单点时限: 10.0 sec
内存限制: 512 MB
Cuber QQ 被分配了一个重要的任务,他要帮助医院协调医疗队列。
等待就诊的每个公民都将被分配一个唯一的数字,从 $1$ 到 $P$ (这里的 $P$ 是当前的人口)。它们将被放入一个队列, $1$ 在 $2$ 前面, $2$ 在 $3$ 前面,以此类推。医院将从这个队列中逐一处理病人。一旦其中一个公民被服务,他们会立即从队伍的前面移到后面。
当然,有时会出现紧急情况——如果一个公民刚刚被一个蒸汽压路机碾过,你不能等到数十个公民去做常规检查后再接受治疗!因此,对于这些(希望是罕见的)情况,可以使用一个快速命令将一个人移到队列的前面。其他国家的相对秩序将保持不变。
给定处理命令和快速命令的顺序,输出当前服务的公民的编号。
第一行两个数$n,p$,表示命令个数和公民个数。
接下来$n$行,每行为一个命令:
1
:表示当前队列首部的公民被服务,被服务后自动放到队列末位。2 x
:表示将编号为$x$的公民移动到队列首部(不进行服务操作)。3
:询问当前队列首部的公民的编号(即下一个要被服务的公民编号)。对于每个3
命令,输出一个数表示当前队列首部的公民的编号。
10 5 2 1 3 2 5 3 1 1 1 3 1 3
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$。