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}$