Uncle Fang is working on his OJ. He is currently dealing with the user ranking problem on the OJ.

There are $n$ users registered on the OJ, numbered $1 \sim n$, and they are initially ranked according to their numbers. Uncle Fang will perform the following four types of operations on these users according to his mood, modifying the users' rankings and numbers:

1. The operation format is 1 x y, which means changing the number of the user with number $x$ to $y$, while the ranking remains unchanged. After executing this operation, you need to output the position of this user in the queue. The data guarantees that $x$ must appear in the queue, and $y$ is a number not currently in the ranking.
2. The operation format is 2 x, which means moving the user with number $x$ to the first place in the ranking. After executing this operation, you need to output the rank of the user with number $x$ before executing this operation.
3. The operation format is 3 x, which means moving the user with number $x$ to the last place in the ranking. After executing this operation, you need to output the rank of the user with number $x$ before executing this operation.
4. The operation format is 4 k, which means querying the number of the user currently ranked at $k$. After executing this operation, you need to output the number of the user currently being operated on.

However, to prevent others from eavesdropping on his work, Uncle Fang has encrypted his operations, changing the formats of the four operations to:

1. 1 x + a y + a
2. 2 x + a
3. 3 x + a
4. 4 k + a

Where $a$ is the output obtained from the previous operation, and initially $a = 0$.

For example: The output obtained from the previous operation is $5$. The input for this operation is: 1 13 15. Since this input is encrypted, the operation you should process is 1 8 10.

Now that you have intercepted all of Uncle Fang's operations, I hope you can provide the results.

Input

The first line of the input contains two space-separated integers $n$ and $m$, representing the initial number of users and the number of operations. Following this are $m$ lines, each representing a query in the format described above.

Output

The output contains $m$ lines. Each line contains an integer, where the integer on the $i$-th line represents the output of the $i$-th operation.

Examples

Input 1

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

Output 1

2
2
2
4
3
5
5
7
8
11

Constraints

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

The input guarantees that for all operations 1, 2, and 3, $x$ must already appear in the queue, and for all operation 1, $1 \le y \le 2 \times 10^8$, and $y$ does not appear in the queue. For all operation 4, it is guaranteed that $1 \le k \le n$.