E - Q2

解説を見る
  • 実行時間制限：2000 ms
  • メモリ制限：1073741824 Bytes
  • 配点：100 点
  • ジャッジ：Batch

問題

QQ 個のクエリが与えられます。
数列 AA ははじめは空です。

各クエリでは TT が与えられ、クエリは以下の3通りです。

  1. T=1T=1 のとき XX が与えられるので AA の末尾に XX を追加
  2. T=2T=2 のとき XX が与えられるので AA の先頭に XX を追加
  3. T=3T=3 のとき AA の先頭を出力し、削除する

各クエリの答えを改行区切りで出力してください。

制約

  • 1≤Q≤1051\leq Q\leq 10^5
  • 1≤X≤1091\leq X\leq 10^9
  • 1≤T≤31\leq T\leq 3
  • クエリ3 が与えられたとき AA の長さは 11 以上
  • 入力はすべて整数

入力

入力は、以下の形式で与えられます。

QQ


Query1Query_1


Query2Query_2


⋮\vdots


QueryQ−1Query_{Q-1}


QueryQQuery_{Q}

QueryiQuery_i は以下の形式のいずれか一つです。

{TXif T=1,2Tif T=3\begin{cases} T\quad X & \text{if } T=1, 2 \\ T & \text{if } T=3 \end{cases}

入力例1

8
1 4
3
2 5
1 6
2 7
3
3
3

出力例1

4
7
5
6