Version Controlled IDE#4094

Version Controlled IDE

8 seconds

64 megabytes

Very hard

Programmers use version control systems to manage files in their projects, but in these systems, versions are saved only when you manually submit. Can you implement an IDE that automatically saves a new version whenever you insert or delete a string?

Positions in the buffer are numbered from $1$ from left to right. Initially, the buffer is empty and in version $0$ . Then you can execute $3$ commands (where $v n o w$ means the version before executing the command, and $L_{v}$ L_v means the length of buffer at version $v$ ):

$1$ $p$ $s$ : insert string $s$ after position $p$ ( $0 \leq p \leq L_{v n o w}$ 0 \leq p \leq L_{vnow}, $p = 0$ p=0 means insert before the start of the buffer). $s$ contains at least $1$ and at most $100$ letters.

$2$ $p$ $c$ : remove $c$ characters starting at position $p$ ( $p \geq 1$ p \geq 1, $p + c \leq L_{v n o w} + 1$ p+c \leq L_{vnow}+1). The remaining characters (if any) will be shifted left, filling the blank.

$3$ $v$ $p$ $c$ : print $c$ characters starting at position $p$ ( $p \geq 1$ p \geq 1, $p + c \leq L_{v} + 1$ p+c \leq L_v+1), in version $v$ ( $1 \leq v \leq v n o w$ 1 \leq v \leq vnow).

The first command is guaranteed to be command $1$ (insert). After executing each command $1$ or $2$ , version is incremented by $1$ .

Input

There is only one test case. It begins with a single integer $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000), the number of commands.

Each of the following $n$ lines contains a command. The total length of all inserted string will not exceed $1000000$ .

Output

Print the results of command $3$ , in order. The total length of all printed strings will not exceed $200000$ .

Obfuscation

In order to prevent you from preprocessing the command, we adopt the following obfuscation scheme:

Each type- $1$ command becomes $1$ $p + d$ p+d $s$

Each type- $2$ command becomes $2$ $p + d$ p+d $c + d$ c+d

Each type- $3$ command becomes $3$ $v + d$ v+d $p + d$ p+d $c + d$ c+d

Where $d$ is the number of lowercase letter 'c' you printed, before processing this command.

For example, the unobfuscated sample input is:

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

After the obfuscation, the sample input would be:

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

This is the real input that your program will read.

Examples

Example 1