King Brian has recently gotten interested in manipulating strings. Today, he decided to study the Suffix Automata (SAM) data structure. However, he found it too complicated, and decided to pose this simpler problem instead:

Given an array of strings $A$, initially filled with a single string $S$, maintain two types of operations:

• C x_i c_i: Copy the string at $A_{x_i}$ and append the character $c_i$ to it. Then, append that new string to the back of $A$.
• Q s_i: Given a query string $s_i$, output the index of the string in $A$ that shares the longest common prefix with $s$. If multiple strings suffice this requirement, the one with the smallest index will be the answer. Additionally, if there is no valid index, -1 is the answer.

Indices are 1-indexed.

Of course, being a king, he isn't content with answering a few measly queries. Instead, he wants you to answer $Q$ of them! Are you up to the challenge?

Constraints

Note: $|x|$ for a string $x$ denotes the length of $x$.

For all subtasks:

$1\le |S|,Q\le {10}^5$

$1\le |s_i|\le 4\times {10}^5$

$S$, all $s_i$, and all $c_i$ will be made of lowercase English letters.

The sum of all $|s_i|$ will be $\le 2\times {10}^6$.

For 3 of 15 available marks, $1\le Q,|S|\le 100$ and the sum of all $|s_i|$ will be $\le 400$.

Input Specification

The first line of input contains $S$ and $Q$.

The next $Q$ lines of input contain a query of one of the types specified above.

Output Specification

For each query, output the answer on a new line.

Sample Input

chad 12
C 1 l
C 1 l
C 3 i
C 4 a
C 2 e
C 6 x
C 5 m
Q cha
Q z
Q chadl
Q chadlliam
Q chadliam

Sample Output

1
-1
2
2
8

Sample Explanation

After all the updates, the array of strings looks like this:

[chad, chadl, chadl, chadli, chadlia, chadle, chadlex, chadliam]