Integer Container


Problem Statement

Implement a data container S implemented as a linked list that will contain a set of integer numbers. The container initially contains an empty list of integers. To manipulate the container S, the following 5 types of operations can be performed:

1.append(W) - Append an integer W to the end of S.

2.delete(k) - Delete the last k integers of S.

3.print(k) - Print the kth integer of S (1 based indexing).

4.undo() - Undo the last (not previously undone) operation of type 1 or 2, reverting D to the state it was in prior to that operation.

5.redo() - Undo the last operation of type 4, reverting S to the state it was in prior to that operation.



Input Format

The first line contains an integer, Q, denoting the number of operations.

Each line i of the subsequent lines (where 0<=**i**<=**Q**) defines an operation to be performed.

Each operation starts with a single integer, t (where t{1,2,3,4,5} ), denoting a type of operation as defined in the Problem Statement above. If the operation requires an argument, t it is followed by its space-separated argument. For example, if t=1 and W=3 , line i will be 1 3.


Constraints

  • 1 <= Q <= 10^6
  • 1 <= k <= |S| (the capacity of the container S).
  • All input integers <= 10^6.
  • It is guaranteed that the sequence of operations given as input is possible to perform.

Output Format

Each operation of type 3 must print the k-th integer on a new line.


Example


Input Example 1

13
1 1
1 2
1 5
1 3
3 2
2 2
4
3 3
5
1 77
3 3
4
3 2

Output Example 1

2
5
77
2


Seleccione el lenguaje