No Name

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer $T$, the number of test cases (1 \leq T \leq 100). Followed by the test cases, each test case starts with a line containing a string $S$ (1 \leq |S| \leq 1000000), followed by one or more lines each describing one of the following operations to perform on $S$ (all indices are zero based, and the quotes are for clarity):

1. "I R X" means insert the string $R$ (1 \leq |R| \leq 1000000) in $S$ at index $X$ (0 \leq X \leq |S|), when $X$ equals $|S|$ this means append $R$ at the end of $S$. For example, the result of inserting xy in abc at position $1$ will be axybc, and the result of inserting xy in abc at position $3$ will be abcxy, and the result of inserting xy in abc at position $0$ will be xyabc.

2. "P X Y" means print the substring of $S$ from $X$ to $Y$, inclusive (0 \leq X \leq Y < |S|). For example the substring from $0$ to $2$ of abc is abc, and the string from $1$ to $1$ of abc is b.

3. "END" Indicates the end of operations for the test case.

Strings $S$ and $R$ will consist of lower case English letters only ('a' to 'z'), and $|S|$ will never get greater than $1000000$ as a result of the operations for any test case. Also, the total number of characters to be printed for any test case will not exceed $1000000$.

Note: Make sure to use fast IO operations, because the input and output files are very large.

Output

For every "P X Y" operation in the input, print one line with the corresponding substring.

Examples