[SCOI2014] 方伯伯的OJ

方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。OJ 上注册了 $n$ 个用户，编号为 $1\sim n$，一开始他们按照编号排名。 方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号： 1. 操作格式为 $1\ \ x\ \ y$，意味着将编号为 $x$ 的用户编号改为 $y$，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证 $x$ 必然出现在队列中，同时，$y$ 是一个当前不在排名中的编号。 2. 操作格式为 $2\ \ x$，意味着将编号为 $x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。 3. 操作格式为 $3\ \ x$，意味着将编号为 $x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。 4. 操作格式为 $4\ \ k$，意味着查询当前排名为 $k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。 但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了： - $1\ \ x+a\ \ y+a$； - $2\ \ x+a$； - $3\ \ x+a$； - $4\ \ k+a$； - 其中 $a$ 为上一次操作得到的输出，一开始 $a=0$。 例如：上一次操作得到的输出是 $5$，这一次操作的输入为：$1\ \ 13\ \ 15$ 因为这个输入是经过加密后的，所以你应该处理的操作是 $1\ \ 8\ \ 10$。 现在你截获了方伯伯的所有操作，希望你能给出结果。

输入的第 $1$ 行包含 $2$ 个用空格分隔的整数 $n$ 和 $m$，表示初始用户数和操作数。此后有 $m$ 行，每行是一个询问，询问格式如上所示。

输出包含 $m$ 行。每行包含一个整数，其中第 $i$ 行的整数表示第 $i$ 个操作的输出。

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

对于 $100\%$ 的数据，$1 \le n \le 10^8$，$1 \le m \le 10^5$。 输入保证对于所有的操作 $1,2,3$，$x$ 必然已经出现在队列中，同时对于所有操作 $1$，$1 \le y \le 2\times 10^8$，并且 $y$ 没有出现在队列中。 对于所有操作 $4$，保证 $1 \le k \le n$。