String Insert and Print

Time limit10sMemory limit256 MB

Summary

Maintain a single string under positional insertions and print the requested substring for each query.

Level: Medium6 of 10
Topics: Tree, String, Implementation
Solved: No attempts yet

Problem

Keep one string $S$ and process insert operations and print operations in the order they are given. An insert operation puts a new string into a chosen position of $S$ , and a print operation writes out a chosen range of $S$ exactly as it stands. No clever idea is needed here, only implementation.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

The first line of each test case contains a string $S$ . ( $1 \le |S| \le 1{,}000{,}000$ )

The operations follow, one per line, and there is at least one operation line. Indices start at 0.

I R X : insert the string $R$ into $S$ at index $X$ . ( $0 \le X \le |S|$ ) After the insertion the first character of $R$ sits at index $X$ . When $X = |S|$ , $R$ is appended to the end of $S$ . For example, when $S$ is abc, I xy 1 gives axybc, I xy 3 gives abcxy, and I xy 0 gives xyabc.
P X Y : print the characters of $S$ from index $X$ through index $Y$ . ( $0 \le X \le Y < |S|$ ) For example, when $S$ is abc, P 0 2 prints abc and P 1 1 prints b.
END : the test case ends here.

$S$ and $R$ consist of lowercase letters only. The length of $S$ never passes 1,000,000 while the operations run, and the number of printed characters summed over all test cases never passes 1,000,000.

The input and the output are both large, so fast input and output are worth using.

Output

Every time a P X Y operation appears, print the matching substring on its own line.

Examples3

Example 1

Input

1
acm
I ac 3
P 0 3
I x 3
I xxxx 6
I pc 6
P 0 11
END

Expected output

acma
acmxacpcxxxx

Example 2

Input

3
abc
I xy 1
P 0 4
END
abc
I xy 3
P 0 4
END
abc
I xy 0
P 0 4
END

Expected output

axybc
abcxy
xyabc

Example 3
Input
```
1
abc
P 0 2
P 1 1
END
```
Expected output
```
abc
b
```