Без імені

Вхідні дані

Ваша програма буде перевірена на одному або кількох тестових випадках. Перший рядок введення містить одне ціле число $T$, яке вказує на кількість тестових випадків (1 \leq T \leq 100). Далі йдуть тестові випадки, кожен з яких починається з рядка, що містить рядок $S$ (1 \leq |S| \leq 1000000), після чого йде один або більше рядків, кожен з яких описує одну з наступних операцій, які потрібно виконати над $S$ (усі індекси починаються з нуля, і лапки наведені для ясності):

1. "I R X" означає вставити рядок $R$ (1 \leq |R| \leq 1000000) у $S$ на індекс $X$ (0 \leq X \leq |S|). Якщо $X$ дорівнює $|S|$, це означає додати $R$ в кінець $S$. Наприклад, результат вставки xy у abc на позицію $1$ буде axybc, а результат вставки xy у abc на позицію $3$ буде abcxy, а результат вставки xy у abc на позицію $0$ буде xyabc.

2. "P X Y" означає вивести підрядок з $S$ від $X$ до $Y$, включно (0 \leq X \leq Y < |S|). Наприклад, підрядок від $0$ до $2$ з abc є abc, а рядок від $1$ до $1$ з abc є b.

3. "END" вказує на кінець операцій для тестового випадку.

Рядки $S$ та $R$ складаються лише з малих англійських літер ('a' до 'z'), і $|S|$ ніколи не перевищить $1000000$ в результаті операцій для будь-якого тестового випадку. Також загальна кількість символів, які потрібно вивести для будь-якого тестового випадку, не перевищить $1000000$.

Примітка: Переконайтеся, що використовуєте швидкі операції вводу-виводу, оскільки файли введення та виводу можуть бути дуже великими.

Вихідні дані

Для кожної операції "P X Y" у введенні, виведіть один рядок з відповідним підрядком.

Приклади