Description

Uncle Fang is building his OJ. Now he is handling the user ranking problem on the OJ. There are $n$ registered users on the OJ, numbered $1\sim n$, and initially they are ranked in ascending order of their IDs.

Depending on his mood, Uncle Fang performs the following four operations to modify users’ ranks and IDs:

1. Operation format $1\ \ x\ \ y$ means: change the user whose ID is $x$ to have ID $y$, while keeping their rank unchanged. After this operation, output that user’s position in the queue. It is guaranteed that $x$ appears in the queue, and $y$ is an ID not currently present in the ranking.
2. Operation format $2\ \ x$ means: move the user whose ID is $x$ to the first position. After this operation, output the rank of user $x$ before the move.
3. Operation format $3\ \ x$ means: move the user whose ID is $x$ to the last position. After this operation, output the rank of user $x$ before the move.
4. Operation format $4\ \ k$ means: query the ID of the user whose current rank is $k$. After this operation, output that user’s ID.

To prevent others from snooping on his work, Uncle Fang encrypts his operations by changing the four formats to:

• $1\ \ x+a\ \ y+a$；
• $2\ \ x+a$；
• $3\ \ x+a$；
• $4\ \ k+a$；
• where $a$ is the output of the previous operation, and initially $a=0$.

Example: if the previous operation’s output is $5$, and this operation’s input is $1\ \ 13\ \ 15$, since the input is encrypted, the operation you should process is $1\ \ 8\ \ 10$.

You have intercepted all of Uncle Fang’s operations. Please produce the results.

Input Format

The first line contains two integers $n$ and $m$, representing the initial number of users and the number of operations. Then follow $m$ lines, each containing one query in the formats described above.

Output Format

Output $m$ lines. The integer on the $i$-th line is the output of the $i$-th operation.

10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

2
2
2
4
3
5
5
7
8
11

Hint

For $100\%$ of the testdata, $1 \le n \le 10^8$, $1 \le m \le 10^5$.

It is guaranteed that for all operations $1,2,3$, $x$ already appears in the queue. For all operations $1$, $1 \le y \le 2\times 10^8$, and $y$ does not appear in the queue.

For all operations $4$, it is guaranteed that $1 \le k \le n$.

Translated by ChatGPT 5