Problem Description

Little C has a queue, and he wants to perform $q$ operations on it. There are four types of operations, with parameters as follows:

$1\ x$: This is the first type of operation, meaning to insert $1,2,3,\cdots,x$ into the back of the queue in order.

$2\ y$: This is the second type of operation, meaning to pop the first $y$ elements from the front of the queue.

$3\ z$: This is the third type of operation, meaning to query the $z$-th element in the queue.

$4$: This is the fourth type of operation, meaning to query the maximum value among all elements in the queue.

You need to help him maintain this queue, and for each operation of the third and fourth type, output the answer to the query.

Input Format

The first line contains two integers $c,q$, where $c$ denotes the test point ID. $c=0$ indicates that this test point is the sample.

The next $q$ lines each contain $1 \sim 2$ integers, representing an operation. The format is given in the Description.

Output Format

For each operation of the third and fourth type, output one integer per line, which is the answer to the query.

0 9
1 5
1 3
2 2
1 4
3 6
3 8
2 4
4
3 3

3
2
4
1

Hint

Sample Explanation #1

After the 4th operation, the elements in the queue in order are $3,4,5,1,2,3,1,2,3,4$.

After the 7th operation, the elements in the queue in order are $2,3,1,2,3,4$.

Sample #2

See queue/queue2.in and queue/queue2.ans in the additional files.

This sample satisfies the constraints of test point $1$.

Sample #3

See queue/queue3.in and queue/queue3.ans in the additional files.

This sample satisfies the constraints of test point $4$.

Sample #4

See queue/queue4.in and queue/queue4.ans in the additional files.

This sample satisfies the constraints of test point $11$.

Sample #5

See queue/queue5.in and queue/queue5.ans in the additional files.

This sample satisfies the constraints of test point $15$.

Sample #6

See queue/queue6.in and queue/queue6.ans in the additional files.

This sample satisfies the constraints of test point $20$.

Constraints

Let $\sum x$ denote the sum of $x$ within a single test point.

For $100\%$ of the testdata, $1 \le q \le 2\times 10^5$, $1 \le x,y,z \le 10^9$, $0 \le \sum x \le 2\times10^{14}$. It is guaranteed that before performing an operation of the second type, the number of elements in the queue is at least $y$; before performing an operation of the third type, the number of elements in the queue is at least $z$; before performing an operation of the fourth type, the number of elements in the queue is greater than $0$.

Special Property A: There is no operation of the second type.

Special Property B: There is no operation of the third type.

Special Property C: There is no operation of the fourth type.

Translated by ChatGPT 5