← 返回题目列表

AtCoder · typical90_bi

061. 甲板(★2)

中文机器翻译题面 查看原题

配点: 2 点

問題文

为了整理你的牌 1 会制作 副牌堆。 最初,牌堆中没有 1 张牌。

从现在开始 Q 进行 次操作。i 番目 (1 \leq i \leq Q) 每次操作执行以下内容:

  • t_i = 1 的时候,整数 x_i 将写有 的牌放到牌堆的最上方
  • t_i = 2 的时候,整数 x_i 将写有 的牌放到牌堆的最下方
  • t_i = 3 时,从牌堆上方开始 x_i 将第 张牌上写的数字写在纸上

t_i = 3 编写一个程序,按照操作顺序输出在操作中写下的整数。

制約

  • 2 \leq Q \leq 10^5
  • 1 \leq t_i \leq 3
  • t_i = 1, 2 什么时候 1 \leq x_i \leq 10^9
  • t_i = 3 什么时候 1 \leq x_i \leq k_i(k_i 是 您也可以写 1 \leq j \leq i 和 t_j = 1, 2 小于 j 的数量)
  • t_i = 1, 2 小于 i 至少 1 有
  • t_i = 3 小于 i 至少 1 有
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

Q
t_1 x_1
t_2 x_2
:
t_Q x_Q

出力

已给出 Q 在 次操作中 t_i = 3 的操作顺序,将导出的整数用换行分隔 1 每行输出


入力例 1

6
1 2
1 1
2 3
3 1
3 2
3 3

出力例 1

1
2
3

牌堆在每次操作后将变为以下状态。

  • 1 第几次操作的立即之后:牌上写的整数按从上到下的顺序 (2) 是
  • 2 第几次操作的立即之后:牌上写的整数按从上到下的顺序 (1, 2) 是
  • 3 从第…次操作开始:卡片上写的整数按从上到下的顺序 (1, 2, 3) 是

因此,写下的数字依次为 1、2、3 。 对于


入力例 2

6
2 1
3 1
2 2
3 1
2 3
3 1

出力例 2

1
1
1

仅进行将卡片放到牌堆最下方的操作。
最初、1 的卡片放入牌组, 用t_i = 3 写出的数总是会被给定 1 。 对于 


入力例 3

6
1 1000000000
2 200000000
1 30000000
2 4000000
1 500000
3 3

出力例 3

1000000000