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}\)