This is the most direct problem ever, you are required to implement some basic string operations like insert and substring. In this problem \textbf{|S|} means the length of the string \textbf{S}. \textit{\textbf{Note}}\textit{: We didn't nd a good name for this problem.} \InputFile Your program will be tested on one or more test cases. The rst line of the input will be a single integer \textbf{T}, the number of test cases (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Followed by the test cases, each test case starts with a line containing a string \textbf{S }(\textbf{1} ≤ \textbf{|S|} ≤ \textbf{1000000}), followed by one or more lines each describing one of the following operations to perform on \textbf{S }(all indices are zero based, and the quotes are for clarity): \begin{enumerate} \item "\textbf{I R X}" means insert the string \textbf{R} (\textbf{1} ≤ \textbf{|R|} ≤ \textbf{1000000}) in \textbf{S} at index \textbf{X} (\textbf{0} ≤ \textbf{X} ≤ \textbf{|S|}), when \textbf{X} equals \textbf{|S|} this means append \textbf{R} at the end of \textbf{S}. For example, the result of inserting \textbf{xy} in \textbf{abc} at position \textbf{1} will be \textbf{axybc}, and the result of inserting \textbf{xy} in \textbf{abc} at position \textbf{3} will be \textbf{abcxy}, and the result of inserting \textbf{xy} in \textbf{abc} at position \textbf{0} will be \textbf{xyabc}. \item "\textbf{P X Y}" means print the substring of \textbf{S} from \textbf{X} to \textbf{Y}, inclusive (\textbf{0} ≤ \textbf{X} ≤ \textbf{Y} < \textbf{|S|}). For example the substring from \textbf{0} to \textbf{2} of \textbf{abc} is \textbf{abc}, and the string from \textbf{1} to \textbf{1} of \textbf{abc} is \textbf{b}. \item "\textbf{END}" Indicates the end of operations for the test case. \end{enumerate} Strings \textbf{S} and \textbf{R} will consist of lower case English letters only ('\textbf{a}' to '\textbf{z}'), and \textbf{|S|} will never get greater than \textbf{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 \textbf{1000000}. \textit{\textbf{Note}}: \textit{Make sure to use fast IO operations, because the input and output les are very large.} \OutputFile For every "\textbf{P X Y}" operation in the input, print one line with the corresponding substring.