B. No Name
time limit per test
4 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

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

The input starts with a line containing a string S (1  ≤  |S|  ≤  200,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|  ≤  200,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, and will be last line of the input.

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

Output

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

Examples
Input
acm
I ac 3
P 0 3
I x 3
I xxxx 6
I pc 6
P 0 11
END
Output
acma
acmxacpcxxxx