Sequence Maintenance

Problem Description

You have a sequence and need to support several operations:

• insert x y: insert the number $y$ after the $x$-th element from the front. If $x = 0$, insert at the very beginning.
• delete x: delete the $x$-th element from the front.
• query k: ask what the $k$-th element from the front is.

Input Format

The first line contains an integer $m$, the number of operations.

The next $m$ lines each contain one of the operations described above.

Output Format

Output several lines: for each query operation, output the answer.

Sample Input

10
insert 0 1
insert 1 2
query 1
query 2
insert 0 3
query 1
delete 1
query 1
insert 1 4
query 2

Sample Output

1
2
3
1
4

Constraints

For $100\%$ of the data, $m \le 10^3$.

For insert operations, $1 \le y \le 10^9$.

For all operations, the position is guaranteed not to exceed the current length of the sequence.