方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。
OJ 上注册了 n 个用户，编号为 1 ∼ 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
数据范围
对于 10% 的数据，1 ≤ n ≤ 10^3
对于 40% 的数据，1 ≤ n ≤ 10^5
对于 100% 的数据，1 ≤ n ≤ 10^8，1 ≤ m ≤ 10^5
输入保证对于所有的操作 1，2，3，x 必然已经出现在队列中，同时对于所有操作 1，1 ≤ y ≤ 2 × 10^8，并且
y 没有出现在队列中。
对于所有操作 4，保证 1 ≤ k ≤ n。