这是有史以来最直接的问题，你需要实现一些基本的字符串操作，如插入和子串提取。

在本题中，$|S|$ 表示字符串 $S$ 的长度。

注：我们没能为这个问题找到一个好名字。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是各个测试用例，每个测试用例以一行包含字符串 $S$（$1 \le |S| \le 1,000,000$）开始，随后是一行或多行描述对 $S$ 执行的操作（所有索引均为从 0 开始，引号仅用于说明）：

1. “I $R$ $X$” 表示在 $S$ 的索引 $X$（$0 \le X \le |S|$）处插入字符串 $R$（$1 \le |R| \le 1,000,000$）。当 $X$ 等于 $|S|$ 时，这意味着将 $R$ 追加到 $S$ 的末尾。例如，在 “abc” 的位置 1 插入 “xy” 的结果是 “axybc”，在位置 3 插入 “xy” 的结果是 “abcxy”，在位置 0 插入 “xy” 的结果是 “xyabc”。
2. “P $X$ $Y$” 表示打印 $S$ 从 $X$ 到 $Y$ 的子串，包含 $X$ 和 $Y$（$0 \le X \le Y < |S|$）。例如，“abc” 从 0 到 2 的子串是 “abc”，“abc” 从 1 到 1 的子串是 “b”。
3. “END” 表示该测试用例的操作结束。

字符串 $S$ 和 $R$ 仅由小写英文字母（'a' 到 'z'）组成，且在任何测试用例中 $|S|$ 永远不会超过 $1,000,000$。此外，每个测试用例需要打印的字符总数不会超过 $1,000,000$。

注：请确保使用快速 I/O，因为输入和输出文件非常大。

输出格式

对于输入中的每一个 “P $X$ $Y$” 操作，打印一行对应的子串。

样例

输入 1

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

输出 1

acma
acmxacpcxxx