8541: AC/DC

J likes playing electric guitar, especially the famous guitar model - Gibson SG Standard. He always composes music with his Gibson SG Standard.

A tune he composes is made up of several notes. Formally, $\mathbf{tune}$ can be regarded as a string consisting of only lower-case letters. Different letters stands for different notes. A substring of a tune is called $\mathbf{phrase}$.

At the beginning, J has a tune of length n. To create new music, J has three operations:

• $1\mathtt{c}$ : Insert a note $c$ at the end of the current tune.
• $2$ : Delete the note at the beginning of the current tune.
• $3\mathtt{t}$ : Query the number of the phrase t appears in the current tune.

Now, J is busy with his new album and invites you to write music together. Can you help him with it?

The first line contains a single integer $(1\le T\le 5)$, the number of test cases. For each test case:

The first line contains a string $S$ of length n(1≤n≤105) indicating the initial tune.

The next line contains one integer m(1≤m≤105) indicating the number of operations.

For the following $m$ lines, the i-th line contains an operation like $1\mathtt{c}$, $2$ or '3 t′.

Let's define the last answer as $lastans$. At the beginning, $lastans=0$.

• For 1 c′, the real operation is c=((c′−′a′)⊕lastans)mod26+′a′.
• For 3 t′, the real operation is for every 1≤i≤∣t∣, ti=((ti′−′a′)⊕lastans)mod26+′a′.

It's guaranteed that c is a lower-case letter. t is a string consisting only of lower-case letters. The sum of the lengths of t of all test cases will not exceed 5×106.

Note that string $S$ may be deleted to an empty string. But it's guaranteed that there will be no operations of type 2 at this time.

1
abcbaba
5
3 ab
3 c
1 a
2
3 da

2
3
1