問題ヴィジュアル

問題文

$(1, 2, \dots, N)$ の並び替え $A$ が与えられる. また, 長さ $Q$ の整数列 $B$ があり, $B$ の第 $j$ 項 $B_j$ は $B_j = N + j$ である. つまり, $$B = (N + 1, N + 2, \dots, N + Q)$$ とする.

この $A, B$ について, 以下の $Q$ 個の処理を順に行え.

• Type I: 1 a の形式で与えられる. $B$ の先頭の項を $b$ として, $B$ からその先頭の項を削除する. その後, $a$ の値によって, 以下のうちのどちらか一方を行う. $a$ は 「$0$ またはこのクエリが与えられた時点で $A$ に存在する整数」であることが保証される.
  • $a = 0$ のとき: $A$ の末尾に $b$ を追加する.
  • $a \neq 0$ のとき: $A$ において $a$ である項の直前に $b$ を挿入する.
  なお, このクエリが与えられる時点で, $B$ は空ではないことが証明できる.
• Type II: 2 の形式で与えられる. $A$ から先頭の項を削除する. このクエリが与えられた時点で, $A$ は空ではないことが保証される.
• Type III: 3 k の形式で与えられる. $A$ における第 $k$ 項を出力する. $k$ はこのクエリが与えられた時点における $A$ の長さを $\lvert A \rvert$ としたとき, $1 \leq k \leq \lvert A \rvert$ であることが保証される.

制約

• $1 \leq N \leq 3 \times 10^5$.
• $A$ は $(1, 2, \dots, N)$ の並び替え.
• $1 \leq Q \leq 3 \times 10^5$.
• 各クエリにおける制約
  • Type I
    • $a$ は「$0$ またはこのクエリが与えられた時点で $A$ に存在する整数」である.
  • Type II
    • このクエリが与えられた時点で, $A$ は空ではない.
  • Type III
    • このクエリが与えられた時点における $A$ の長さを $\lvert A \rvert$ としたとき, $1 \leq k \leq \lvert A \rvert$ である.
• 入力は全て整数である.
• Type III のクエリが $1$ 個以上与えられる.

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
${\rm Query}_1$
${\rm Query}_2$
$\vdots$
${\rm Query}_Q$

• Type I

  $1$ $a$

• Type II

  $2$

• Type III

  $3$ $k$

出力

$Q$ 個のクエリの内, Type III のクエリが $Q_3$ 個であったとする. このとき, 出力は $Q_3$ 行からなる.

第 $r~(1 \leq r \leq Q_3)$ 行には, $r$ 番目に与えられた Type III における解答を整数で出力せよ.

最後に改行を忘れないこと.

サンプル

5
3 5 2 4 1
7
1 2
1 0
2
3 5
2
1 6
3 1

1
8

1
1
9
2
1 0
3 1
2
1 0
3 1
2
1 0 
3 1

2
3
4