Peppa loves playing with strings. She has a string $S$ and performs a series of operations, 'FRAPIC', on it. As a good friend of Peppa, your task is to determine the final state of the string $S$ after all the FRAPIC operations.

Input

The first line contains the initial string $S$, which includes ASCII characters but excludes spaces.
The second line contains an integer $N$, the number of FRAPIC operations.
The next $N$ lines describe the FRAPIC operations, one per line. Each FRAPIC operation is one of the following types:
1. F l r: Flip the substring $S[l..r]$.
2. R l r s: Replace the substring $S[l..r]$ with the string $s$. ($|s| = r-l+1$)
3. A s: Add the string $s$ to the end of $S$.
4. P s: Output the position of the first occurrence of the substring $s$ in $S$ in a single line. If not found, output $-1$ in a single line.
5. I i s: Insert the string $s$ at position $i$.
6. C l r: Cut and remove the substring $S[l..r]$.

Output

When the FRAPIC operation is P, output the position of the substring $s$ in $S$ in a single line. If not found, output $-1$ in a single line.
After all operations, output the final state of the string $S$.

Constraints

For all cases,
$1 \le |S|, |s|, N \le 10^3$
$1 \le l, r, i \le |S|$
It is guaranteed that $1 \le |S| \le 10000$ at any time.
Subtask 1 (10%): The input only contains the FRAPIC operation F
Subtask 2 (10%): The input only contains the FRAPIC operation R
Subtask 3 (10%): The input only contains the FRAPIC operation A
Subtask 4 (10%): The input only contains the FRAPIC operation P
Subtask 5 (10%): The input only contains the FRAPIC operation I
Subtask 6 (10%): The input only contains the FRAPIC operation C
Subtask 7 (40%): No additional constraints