Matching in a Tree

Lizi studied Trie in Data Structure class. He learned that Trie is a rooted tree to store some strings. There is a character on each edge of a Trie. In this problem, valid characters are only lowercase Latin letters.

There is a Trie T. At the beginning, the Trie only has a root, which is labeled 0.

Now you also have a string S ( At the beginning, it's a empty string.)

We use $P_i$ to denote the string concatenated with characters on the path from the root to node labeled i.

We use $Q_i$ to denote the prefix of the string S, which length is i.

Now give you m operations of the following forms.

ADD u v c

Insert a node labeled v. The node's father is u, and the character between the node and its father is c. Assume the label of the node is exactly the max label of the tree's node +1 .

ASK p1 p2 t

Ask whether there exists a string $Q_l$($0 \le p1\le l \le p2 \le Length(S)$ ), which is meanwhile a substring of $P_t$. Output 'yes' or 'no'.

INS p1 p2

Add a charcter c at the end of the string. Unluckly, we only know the character is between p1 and p2. That is to say, $'a'\le p1\le c\le p2\le 'z'$.

The input contains multiple test cases.

There are at most 7 test cases.

For each test case, the first line contains one integer m($1\leq m \leq 10^6$).
Then next m lines contain operations ADD u v c , ASK p1 p2 t or INS p1 p2.

At the end, the length of the string S is at most $10^3$.

For each operation 2, if the answer is yes, print 'yes', otherwise, print 'no'.

Since the output may be very large, denote $q$ as the number of operation 2, and $f_i(1\leq i\leq q)$ as the answer of the $i$-th query(regard 'yes' as $1$ and 'no' as $2$). For each test case, print a single line containing an integer, denoting the following thing:

\begin{eqnarray*}
\left(\sum_{i=1}^q 233^{q-i}f_i\right)\bmod 1000000007
\end{eqnarray*}

7
ADD 0 1 a
ADD 0 2 c
INS a a
ASK 1 1 1
INS a c
ASK 1 2 1
ASK 2 2 2

54524

If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）