Problem Description

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, a $\bf{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 $\bf{phrase}$.

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

- $\mathtt{1\ c}$ : Insert a note $c$ at the end of the current tune.
- $\mathtt{2}$ : Delete the note at the beginning of the current tune.
- $\mathtt{3\ 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?

Input

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

The first line contains a string $S$ of length $n$ $(1\le n \le 10^5)$ indicating the initial tune.

The next line contains one integer $m$ $(1\le m\le 10^5)$ indicating the number of operations.

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

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

- For $\mathtt{1\ c'}$, the real operation is $c = ((c'- 'a') \oplus lastans)\bmod 26 + 'a'$.
- For $\mathtt{3\ t'}$, the real operation is for every $1\le i\le |t|,\ t_i = ((t'_i-'a') \oplus lastans)\bmod 26 + '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 \times 10^6$.

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.

Output

For each query $\mathtt{3\ t}$, print a single integer in a single line indicating the answer.

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

2
3
1