G. Text Editor

★★★★★

0 votes

Skip List, Cartesian-Tree, Data Strucrures, Hard, Rope, Treap

Details

Problem

After losing the nintendo game and the bet with King, Saitama now tries his hand at programming! He is trying to build a text-editor, but alas, he is too dumb to write even a line of code! Let's assume that everything written inside the text-editor is a large string. Initially there is no text in text-editor, i.e the string is empty. He wants to perform three kinds of operations on this string.

$1 \hspace{4pt} y \hspace{4pt} p$ : Print the substring of size $y$ starting from pos $p$ .

$2 \hspace{4pt} x \hspace{4pt} p$ : Insert string $x$ at position $p$ in the string.

$3 \hspace{4pt} l \hspace{4pt} r$ : Delete all characters in range $[l, r]$ in string.

Please help him implement this humongous task.

Input

First line contains $q$ , i.e number of queries

Next $q$ lines contain queries.

Output

For every query of type $1$ , print the substring of given size from given position.

It is guaranteed that all queries are valid. The first position in string is index $0$ .

Constraints

$q \le 2\cdot10^5$

$\text{Sum of } |y _i| \text{ over all queries} \le 2 \cdot 10^{6}$

$\text{Sum of } |x _i| \text{ over all queries} \le 2\cdot10^{6}$

Sample Input

5
2 thisisaneasyproblem 0
2 not 6
1 22 0
3 6 8
1 13 6

Sample Output

thisisnotaneasyproblem
aneasyproblem

Time Limit: 2

Memory Limit: 1024

Source Limit:

Explanation

Let string be $s$ .

Initially $s$ is empty.

After the $1^{st}$ query, $s = thisisaneasyproblem$ ,

After the $2^{nd}$ query, $s = thisisnotaneasyproblem$

In $3^{rd}$ query, the substring of size $22$ from position $1$ is $thisisnotaneasyproblem$

After $4^{th}$ query, $s = thisisaneasyproblem$

In $5^{th}$ query, the substring of size $13$ from position $7$ is $aneasyproblem$