Encrypted User Ranking Operations

There are \(n\) users registered on an online judge, numbered from \(1\) to \(n\). Initially, they are ranked according to their numbers (i.e. the user with number \(1\) is ranked first, \(2\) second, etc.).

Uncle Fang is performing a series of operations on these users which affect their ranking and their numbers. There are four types of operations. In the original (unencrypted) format, the operations are as follows:

1. Operation: \(1\ x\ y\). Change the number of the user with number \(x\) to \(y\) without changing the ranking order. After this operation, output the position (rank) of this user in the queue. It is guaranteed that \(x\) currently exists in the ranking, and \(y\) is not used by any user in the ranking.
2. Operation: \(2\ x\). Raise the user with number \(x\) to the first position. Before the move, output the current rank of the user \(x\).
3. Operation: \(3\ x\). Lower the user with number \(x\) to the last position. Before the move, output the current rank of the user \(x\).
4. Operation: \(4\ k\). Query the number of the user who is currently at rank \(k\). Output the user number.

To hide his work from prying eyes, Uncle Fang has encrypted his operations. The encryption is performed by adding a number \(a\) (which is the output of the previous operation, with \(a=0\) initially) to each numeric parameter. That is, the encrypted operations are:

• \(1\ (x+a)\ (y+a)\)
• \(2\ (x+a)\)
• \(3\ (x+a)\)
• \(4\ (k+a)\)

For example, if the previous operation produced an output of \(5\), then an encrypted input 1 13 15 should be interpreted as \(1\ 8\ 10\) because \(13-5=8\) and \(15-5=10\).

You are given a series of operations on the ranking. Process the operations and output the result of each operation accordingly.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of users and the number of operations respectively.

Then follow \(m\) lines, each line representing one encrypted operation in one of the following formats:

• 1 x y
• 2 x
• 3 x
• 4 k

Remember that the actual parameters for each operation should be obtained by subtracting \(a\) (the previous operation's output, with \(a=0\) initially) from the given numbers (except the leading type number which is not encrypted).

outputFormat

For each operation, output one line containing a single integer — the output as described below:

• For operation \(1\): output the current rank (position) of the user after changing the number.
• For operations \(2\) and \(3\): output the user's rank before the repositioning.
• For operation \(4\): output the number of the user who is at the given rank.

sample

5 5
1 1 100
2 101
3 4
4 6
1 9 204

1
1
3
4
4

</p>