Fake Daruma Otoshi

問題文

処理犬くんは、 $K$ 種類の色の積み木を持っており、それぞれの色に、$1,2,3, \dots,K$ と番号が付けられています。 また、積み木は各色で $10^9$ 個ずつ、つまり全部で $K \times 10^9$ 個の積み木を持っています。 処理犬くんは、それらの積み木を使って「似非だるま落とし」を遊んでいます。

「似非だるま落とし」の遊び方は、以下の二種類の操作のうちのいずれかを延々と繰り返す、というものです。

• 縦に積まれている積み木の上に、新たな積み木を載せる。
  即ち、この操作の前の積まれた積み木の数が $M$ のとき、操作後の積まれた積み木の数は $M+1$ になる。
• 縦に積まれている積み木のうち、いずれかの積み木を横から叩き、落とす。
  落とした積み木より上に積まれていた積み木は、順番を保ったまま下に落下する。
  即ち、この操作の前の積まれた積み木の数が $M$ のとき、操作後の積まれた積み木の数は $M-1$ になる。

はじめに、積み木は $N$ 個積まれており、下から $i$ 番目の積み木の色の番号が $S_i$ で与えられます。 $(1 \leq i \leq N)$
その後の処理犬くんの $Q$ 回の操作がクエリとして与えられるので、順番に処理してください。 クエリは以下の $2$ 種類のいずれかです。

• 1 c 色の番号が $c$ の積み木を、縦に積まれている積み木の上に新たに載せる。
• 2 p 下から $p$ 番目の積み木を、横から叩き、落とす。この時、落とした積み木の色の番号を出力する。ただし、このクエリを処理する時点で、積み木が $p+1$ 個以上積まれていることが保証される。

なお、処理犬くんは、「似非だるま落とし」のプロフェッショナルなので、失敗して積んだ積み木を倒してしまうことはありません。

制約

• $1 \leq N \leq 100$
• $1 \leq K \leq 100$
• $1 \leq S_i \leq K \ (1 \leq i \leq N)$
• $1 \leq Q \leq 100$
• $1 \leq c \leq K$
• $2$ 種類目のクエリ 2 p が与えられるとき、このクエリを処理する時点で、積み木が $p+1$ 個以上積まれていることが保証される。
• 入力は全て整数である。

入力

N K Q
S_1 S_2 S_3 ... S_N
query_1
query_2
query_3
.
.
.
query_Q

• $1$ 行目に、最初に積まれている積み木の数 $N$ 、 積み木の色の種類数 $K$ 与えられるクエリの数 $Q$ が空白区切りで与えられます。
• $2$ 行目に、積まれている積み木の色の番号が、下から順に与えられます。
• $3$ 行目以降に、順にクエリが与えれます。
• $query_i$ は $i$ 個目のクエリであり、以下のいずれかの形式で与えられます。

1 c

2 p

出力

$2$ 種類目のクエリの個数を $q$ 個として、 $q$ 行で出力してください。$i \, (1 \leq i \leq q)$ 行目には $i$ 個目の $2$ 種類目のクエリに対する答えを出力してください。

入力例 1

3 3 5
1 2 3
2 1
2 1
1 3
1 1
2 2

出力例 1

1
2
3

以下では、積まれている積み木の状態を $[S_1,S_2,S_3, \dots]$ のような形式で表し、これは下から $1$ 番目の積み木の色の番号が $S_1$ 、下から $2$ 番目の積み木の色の番号が $S_2$ 、下から $3$ 番目の積み木の色の番号が $S_3$ $\dots$ であることを表します。

• はじめに、積み木の状態は $[1,2,3]$ です。
• $1$ 番目のクエリでは、下から $1$ 番目の積み木を横から叩いて落とします。よって、$1$ を出力し、積み木の状態は、 $[2,3]$ となります。
• $2$ 番目のクエリでは、下から $1$ 番目の積み木を横から叩いて落とします。よって、$2$ を出力し、積み木の状態は、 $[3]$ となります。
• $3$ 番目のクエリでは、色の番号が $3$ の積み木を積まれている積み木の上に、新たに載せます。よって、積み木の状態は、 $[3,3]$ となります。
• $4$ 番目のクエリでは、色の番号が $1$ の積み木を積まれている積み木の上に、新たに載せます。よって、積み木の状態は、 $[3,3,1]$ となります。
• $5$ 番目のクエリでは、下から $2$ 番目の積み木を横から叩いて落とします。よって、$3$ を出力し、積み木の状態は、 $[3,1]$ となります。

入力例 2

3 3 3
1 2 3
1 1
1 1
1 1

出力例 2

何も出力する必要が無いこともあります。