2020级计算机专业《面向对象程序设计(C++)》

H. 医疗队列

单点时限: 10.0 sec

内存限制: 512 MB

Cuber QQ 被分配了一个重要的任务,他要帮助医院协调医疗队列。

等待就诊的每个公民都将被分配一个唯一的数字,从 $1$ 到 $P$ (这里的 $P$ 是当前的人口)。它们将被放入一个队列, $1$ 在 $2$ 前面, $2$ 在 $3$ 前面,以此类推。医院将从这个队列中逐一处理病人。一旦其中一个公民被服务,他们会立即从队伍的前面移到后面。

当然,有时会出现紧急情况——如果一个公民刚刚被一个蒸汽压路机碾过,你不能等到数十个公民去做常规检查后再接受治疗!因此,对于这些(希望是罕见的)情况,可以使用一个快速命令将一个人移到队列的前面。其他国家的相对秩序将保持不变。

给定处理命令和快速命令的顺序,输出当前服务的公民的编号。

输入格式

第一行两个数$n,p$,表示命令个数和公民个数。

接下来$n$行,每行为一个命令:

  • 1:表示当前队列首部的公民被服务,被服务后自动放到队列末位。
  • 2 x:表示将编号为$x$的公民移动到队列首部(不进行服务操作)。
  • 3:询问当前队列首部的公民的编号(即下一个要被服务的公民编号)。

输出格式

对于每个3命令,输出一个数表示当前队列首部的公民的编号。

样例

Input
10 5
2 1
3
2 5
3
1
1
1
3
1
3
Output
1
5
3
4

提示

样例说明解释

开始队列为:1 2 3 4 5

第一个命令执行后队列为:1 2 3 4 5(1本来就在队首)

第二个命令执行后队列为:1 2 3 4 5,输出1

第三个命令执行后队列为:5 1 2 3 4

第四个命令执行后队列为:5 1 2 3 4,输出5

第五个命令执行后队列为:1 2 3 4 5

第六个命令执行后队列为:2 3 4 5 1

第七个命令执行后队列为:3 4 5 1 2

第八个命令执行后队列为:3 4 5 1 2,输出3

第九个命令执行后队列为:4 5 1 2 3

第十个命令执行后队列为:4 5 1 2 3,输出4

数据范围约定

对于$30\%$数据满足:$1 \leq n,p \leq 10$。

对于$70\%$数据满足:$1 \leq n,p \leq 5 \times 10^3$。

对于$100\%$数据满足:$1 \leq n,p \leq 10^6$。