Контрольована версіями IDE#4094

Контрольована версіями IDE

8 секунд

64 мегабайти

Дуже складна

Програмісти часто використовують системи контролю версій для управління файлами у своїх проектах. Однак у цих системах версії зберігаються лише тоді, коли ви вручну надсилаєте зміни. Чи можете ви створити IDE, яке автоматично зберігає нову версію щоразу, коли ви вставляєте або видаляєте рядок?

Позиції в буфері нумеруються з $1$ зліва направо. Спочатку буфер порожній і знаходиться у версії $0$ . Потім ви можете виконати $3$ типи команд (де $v n o w$ означає версію перед виконанням команди, а $L_{v}$ L_v — це довжина буфера у версії $v$ ):

$1$ $p$ $s$ : вставити рядок $s$ після позиції $p$ ( $0 \leq p \leq L_{v n o w}$ 0 \leq p \leq L_{vnow}, $p = 0$ p=0 означає вставити перед початком буфера). $s$ містить від $1$ до $100$ літер.

$2$ $p$ $c$ : видалити $c$ символів, починаючи з позиції $p$ ( $p \geq 1$ p \geq 1, $p + c \leq L_{v n o w} + 1$ p+c \leq L_{vnow}+1). Залишені символи (якщо є) будуть зміщені вліво, заповнюючи порожнечу.

$3$ $v$ $p$ $c$ : вивести $c$ символів, починаючи з позиції $p$ ( $p \geq 1$ p \geq 1, $p + c \leq L_{v} + 1$ p+c \leq L_v+1), у версії $v$ ( $1 \leq v \leq v n o w$ 1 \leq v \leq vnow).

Перша команда завжди буде командою $1$ (вставка). Після виконання кожної команди $1$ або $2$ , версія збільшується на $1$ .

Вхідні дані

Є лише один тестовий випадок. Він починається з одного цілого числа $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000), що вказує на кількість команд.

Кожен з наступних $n$ рядків містить команду. Загальна довжина всіх вставлених рядків не перевищуватиме $1000000$ .

Вихідні дані

Виведіть результати команд $3$ у порядку. Загальна довжина всіх виведених рядків не перевищуватиме $200000$ .

Обфускація

Щоб запобігти попередній обробці команд, ми застосовуємо наступну схему обфускації:

Кожна команда типу- $1$ стає $1$ $p + d$ p+d $s$

Кожна команда типу- $2$ стає $2$ $p + d$ p+d $c + d$ c+d

Кожна команда типу- $3$ стає $3$ $v + d$ v+d $p + d$ p+d $c + d$ c+d

Де $d$ — це кількість малих літер 'c', які ви вивели, перед обробкою цієї команди.

Наприклад, необфускований зразок введення виглядає так:

6
1 0 abcdefgh
2 4 3
3 1 2 5
3 2 2 3
1 2 xy
3 3 2 4

Після обфускації зразок введення буде:

6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6

Це реальний вхід, який ваша програма буде читати.

Приклади

Приклад 1