[Scoi2014]方伯伯的Oj

时间限制:6s      空间限制:256MB

题目描述

方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:
1.操作格式为1 x y,意味着将编号为z的用户编号改为V,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时1,是一个当前不在排名中的编号。
2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
3.操作格式为3 x,意味着将编号为z的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
4.操作格式为4 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                       
25                        
37                         
28                        
2 10                       
2 11                       
3 14                       
2 18                      
4 9  

样例输出

2
2
2
4
3
5
5
7
8
11

提示

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


题目来源

By 佚名提供