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

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

2
5
77
2