No Name
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 nd a good name for this problem.
Input
Your program will be tested on one or more test cases. The rst 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| ≤ 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):
"I R X" means insert the string R (1 ≤ |R| ≤ 1000000) 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.
"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.
"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 les are very large.
Output
For every "P X Y" operation in the input, print one line with the corresponding substring.