Version-Controlled IDE

Many programmers use a version control system to manage the files in a project. Such systems have a drawback, however: a version is recorded only when the user explicitly saves.

Here you will implement an IDE that automatically saves a new version every time a string is inserted or deleted.

Positions in the buffer are numbered from left to right starting at 1. Initially the buffer is empty and the version number is 0.

Let $L[v]$ be the length of the buffer at version $v$, and let $v_{now}$ be the version number just before a command is executed. The IDE supports three commands:

• 1 p s: insert the string $s$ right after position $p$ ($0 \le p \le L[v_{now}]$). If $p = 0$, insert at the very front of the buffer. The length of $s$ is between 1 and 100.
• 2 p c: delete $c$ characters starting at position $p$ ($p \ge 1$, $p + c \le L[v_{now}] + 1$).
• 3 v p c: output $c$ characters starting at position $p$ in version $v$ ($p \ge 1$, $p + c \le L[v] + 1$).

The first command is always a type-1 command. Executing a type-1 or type-2 command increases the version by 1; a type-3 command does not change the version.

The first line contains the number of commands $T$ ($1 \le T \le 50\,000$). Each of the next $T$ lines contains one command. The total length of all inserted strings does not exceed $1\,000\,000$.

To prevent preprocessing the input, each command is encoded. Let $d$ be the number of lowercase c characters printed so far (initially $d = 0$).

• A type-1 command is given as 1 p+d s,
• a type-2 command is given as 2 p+d c+d,
• a type-3 command is given as 3 v+d p+d c+d.

So after reading each command, subtract $d$ from every numeric argument to recover the real values $p$, $c$, and $v$.

Every time a type-3 command is executed, print its resulting string on its own line. The total length of the printed strings does not exceed $200\,000$.