Problem Statement:
This is the most direct problem ever, you are required to implement some basic string operations like insert and substring.

In this problem |S| means the length of the string S.

Note: We didn't find a good name for this problem.

Input Format:
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 ≤ T ≤ 100). Followed by the test cases, each test case starts with a line containing a string S (1 ≤ |S| ≤ 1, 000, 000), 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 ≤ |R| ≤ 1, 000, 000) in S at index X (0 ≤ X ≤ |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 ≤ X ≤ 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 1,000,000 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 1,000,000.

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

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

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

Sample Output:
acma acmxacpcxxxx

Added by: abdelkarim
Added at: 2014-02-22 19:28:44 UTC
Time Limit: 1.5 seconds
Partial score: No
Source:ACM Arab Collegiate Programming Contest 2012