#2212. 「SCOI2014」方伯伯的 OJ

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

方伯伯正在做他的 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

现在你截获了方伯伯的所有操作,希望你能给出结果。

输入格式

输入的第一行包含两个用空格分隔的整数 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 \leq n \leq 10^8,\ 1 \leq m \leq 10^5
输入保证对于所有的操作, x 必然已经出现在队列中,同时对于所有操作 1 1 \leq y \leq 2 \times 10^8 ,并且 y 没有出现在队列中。
对于所有操作 4,保证 1 \leq k \leq n