#P18709. Moniphant Sleep
Moniphant Sleep
Moniphant Sleep
你好,这里是 Moniphant!他有一个问题想请你解决。

Moniphant 发现自己可以进入不同深度的睡眠,在每一层都会遇到一个 Mofunfun。形式化地,有以下四种操作:
- 睡觉:进入下一层睡眠,即深度增加 1。
- 醒来:从当前层回到上一层,即深度减少 1。
- 对 Mofunfun 说“你是猪!”:激怒当前层的 Mofunfun,使它生气。
- Mofunfun 的报复:每一层的 Mofunfun 都尝试报复,只有生气的 Mofunfun 能够成功。成功的报复会使 Moniphant 回到所有生气的 Mofunfun 中层数最小、也就是最浅的那一层。报复之后,Mofunfun 不再生气。如果没有 Mofunfun 生气,则忽略这次操作。
下图的四幅原图依次对应上述四种操作。

注意:当 Moniphant 回到更浅的层时,被离开的更深层中的 Mofunfun 会消失。
现在有 个 Moniphant,编号为 。你需要对编号属于区间 的所有 Moniphant 执行上述某种操作,或者询问某个 Moniphant 当前所在的睡眠深度。
在问题开始前,每个 Moniphant 都已执行了 次“睡觉”(第 1 种操作),即初始深度为 ,且没有 Mofunfun 生气。
输入格式
第一行包含两个整数 (),分别表示 Moniphant 的数量和操作数。
接下来 行,每行包含三个整数 (,)。
- 如果 ,对编号在 中的所有 Moniphant 执行第 种操作。
- 如果 ,保证 ,你需要输出编号为 的 Moniphant 的睡眠深度。
输出格式
对每个第 5 种操作,输出一行一个整数,表示所询问的睡眠深度。
样例 1 输入
1 9
1 1 1
1 1 1
1 1 1
3 1 1
2 1 1
1 1 1
1 1 1
4 1 1
5 1 1
样例 1 输出
500004
样例 2 输入
3 7
2 1 3
3 1 3
1 1 3
1 1 3
5 1 1
4 1 3
5 1 1
样例 2 输出
500001
499999