#AWC118D. 医院接待
医院接待
AtCoder-awc0118_d
题目描述
高桥负责医院接待处的排队管理。接待处只有一条队伍,患者们按照到达顺序排在队尾。
不过,这家医院有紧急患者的优先卡。持有优先卡的患者可以在队伍中的指定位置插队。高桥需要在每次插队操作后,准确地维护整个队列的状态。
起初队列为空。接下来会依次给出 个操作,操作共有 种:
操作 :患者 排到队尾;
操作 :持有优先卡的患者 插入到队伍的第 个位置。插入完成后,队伍中第 个位置上的患者就是 ,原本位于第 个位置及其之后的患者依次往后挪一位;
操作 :队伍最前面的患者被接待,并从队列中移除。此时需要输出该患者的编号。
注意,同一个患者编号可能在不同操作中多次出现,但每次出现都视为不同的患者,独立地加入队列。
输入格式
第一行输入一个整数 代表操作数量。
此后 行,每行先输入一个整数 代表操作类型,随后在同一行:
若 ,输入一个整数 代表排到队尾的患者编号;
若 ,输入两个整数 $x, k \left(1 \leqq x \leqq 10^9;\ 1 \leqq k \leqq \mathrm{len}+1\right)$ 代表插队患者的编号与插入位置;
若 ,不需要再输入其他内容。
其中, 代表该次操作前队伍中的患者数量。特别地,当 时,患者被插入到队尾。保证执行操作 时队伍非空。
输出格式
对于每次操作 ,在一行上输出一个整数,代表被接待患者的编号。
测试样例
7
1 10
1 20
2 30 2
3
2 40 1
3
3
10
40
30
样例 1 解释
初始时队伍为空,操作过程如下:
执行 :队伍变为 ;
执行 :队伍变为 ;
执行 : 插入到第 个位置,队伍变为 ;
执行 :队首的 被接待,输出 ,队伍变为 ;
执行 : 插入到第 个位置,队伍变为 ;
执行 :队首的 被接待,输出 ,队伍变为 ;
执行 :队首的 被接待,输出 ,队伍变为 。
因此依次输出 。
6
2 5 1
1 5
2 7 3
3
3
3
5
5
7
18
1 100
1 200
2 300 1
1 400
2 500 3
3
2 600 5
3
1 700
2 800 2
3
3
2 900 1
1 1000
2 1100 4
3
3
3
300
100
500
800
900
200
400
40
1 1000000000
1 1
1 2
2 999999999 1
2 123456789 3
3
1 3
2 4 6
2 5 2
3
3
1 6
2 7 1
2 8 4
1 9
3
2 10 9
1 11
2 12 5
3
3
2 13 1
2 14 10
1 15
3
1 16
2 17 7
2 18 14
3
3
3
2 19 1
1 20
2 21 13
3
1 22
2 23 15
3
3
3
999999999
1000000000
5
7
123456789
1
13
8
2
12
19
3
4
6
2
2 1000000000 1
3
1000000000