Maintaining a Dynamic Queue with Multiple Operations

You are given an initially empty queue. You need to perform q operations on the queue. There are four types of operations described as follows:

• 1 x: Append the sequence 1, 2, 3, ..., x to the tail of the queue.
• 2 y: Remove the first y elements from the head of the queue.
• 3 z: Query and output the value of the z^th element in the queue (1-indexed).
• 4: Query and output the maximum value among all elements currently in the queue.

For every operation of type 3 and type 4, print the corresponding answer.

Note: It is guaranteed that each query operation is valid (i.e. the query index exists and there are at least as many elements as needed to be removed).

The operations involve the following formula: $$1\ x: \quad 1,2,3,\cdots,x$$

inputFormat

The first line of input contains a single integer q, the number of operations.

Each of the following q lines contains one operation in one of the following formats:

• For type 1: 1 x
• For type 2: 2 y
• For type 3: 3 z
• For type 4: 4

outputFormat

For each operation of type 3 and type 4, output the corresponding result on a new line.

sample

6
1 3
4
3 2
2 2
4
3 1

3
2
3
3