#AWC118D. 医院接待

医院接待

AtCoder-awc0118_d

题目描述

\hspace{15pt}高桥负责医院接待处的排队管理。接待处只有一条队伍,患者们按照到达顺序排在队尾。

\hspace{15pt}不过,这家医院有紧急患者的优先卡。持有优先卡的患者可以在队伍中的指定位置插队。高桥需要在每次插队操作后,准确地维护整个队列的状态。

\hspace{15pt}起初队列为空。接下来会依次给出 qq 个操作,操作共有 33 种:

∙ \hspace{23pt}\bullet\,操作 11:患者 xx 排到队尾;

∙ \hspace{23pt}\bullet\,操作 22:持有优先卡的患者 xx 插入到队伍的第 kk 个位置。插入完成后,队伍中第 kk 个位置上的患者就是 xx,原本位于第 kk 个位置及其之后的患者依次往后挪一位;

∙ \hspace{23pt}\bullet\,操作 33:队伍最前面的患者被接待,并从队列中移除。此时需要输出该患者的编号。

\hspace{15pt}注意,同一个患者编号可能在不同操作中多次出现,但每次出现都视为不同的患者,独立地加入队列。

输入格式

\hspace{15pt}第一行输入一个整数 q(1≦q≦2×105)q \left(1 \leqq q \leqq 2 \times 10^5\right) 代表操作数量。

\hspace{15pt}此后 qq 行,每行先输入一个整数 t(1≦t≦3)t \left(1 \leqq t \leqq 3\right) 代表操作类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 t=1t = 1,输入一个整数 x(1≦x≦109)x \left(1 \leqq x \leqq 10^9\right) 代表排到队尾的患者编号;

∙ \hspace{23pt}\bullet\,若 t=2t = 2,输入两个整数 $x, k \left(1 \leqq x \leqq 10^9;\ 1 \leqq k \leqq \mathrm{len}+1\right)$ 代表插队患者的编号与插入位置;

∙ \hspace{23pt}\bullet\,若 t=3t = 3,不需要再输入其他内容。

\hspace{15pt}其中,len\mathrm{len} 代表该次操作前队伍中的患者数量。特别地,当 k=len+1k = \mathrm{len}+1 时,患者被插入到队尾。保证执行操作 33 时队伍非空。

输出格式

\hspace{15pt}对于每次操作 33,在一行上输出一个整数,代表被接待患者的编号。

测试样例

7
1 10
1 20
2 30 2
3
2 40 1
3
3
10
40
30

样例 1 解释

\hspace{15pt}初始时队伍为空,操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "1 10"\texttt{"1 10"}:队伍变为 {10}\{10\};

∙ \hspace{23pt}\bullet\,执行 "1 20"\texttt{"1 20"}:队伍变为 {10,20}\{10, 20\};

∙ \hspace{23pt}\bullet\,执行 "2 30 2"\texttt{"2 30 2"}:3030 插入到第 22 个位置,队伍变为 {10,30,20}\{10, 30, 20\};

∙ \hspace{23pt}\bullet\,执行 "3"\texttt{"3"}:队首的 1010 被接待,输出 1010,队伍变为 {30,20}\{30, 20\};

∙ \hspace{23pt}\bullet\,执行 "2 40 1"\texttt{"2 40 1"}:4040 插入到第 11 个位置,队伍变为 {40,30,20}\{40, 30, 20\};

∙ \hspace{23pt}\bullet\,执行 "3"\texttt{"3"}:队首的 4040 被接待,输出 4040,队伍变为 {30,20}\{30, 20\};

∙ \hspace{23pt}\bullet\,执行 "3"\texttt{"3"}:队首的 3030 被接待,输出 3030,队伍变为 {20}\{20\}。

\hspace{15pt}因此依次输出 10,40,3010, 40, 30。

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