P3285 [SCOI2014] Uncle Fang's OJ

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.

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 $m$ lines. The integer on the $i$-th line is the output of the $i$-th operation.

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