問題文

$N$ 人の競プロやったことない奴(以降、地球人と省略)が左右に並んでいます。左から $i$ 番目の地球人の番号は $i$ でレート(自称)は $A_i$ です。

岩井星人さんは $Q$ 回、ポリオミノを地球人にぶつけます。

具体的には $i$ 回目の情報はそれぞれ $2$ 個の整数の組 ($c, X$) で以下のように与えられます。

• $c=1$ のとき：$X$ よりレート(自称)が高い地球人のうち最も左にいる地球人にポリオミノをぶつける。
• $c=2$ のとき：$X$ よりレート(自称)が高い地球人のうち最も右にいる地球人にポリオミノをぶつける。

ポリオミノをぶつけられた地球人は列から外れ、それ以降列に戻ってくることはありません。

岩井星人さんが $Q$ 回投げたポリオミノによって列から外れる地球人の番号をそれぞれ出力してください。 ただし、誰も列から外れない場合は $-1$ を出力してください。

制約

• $1 \leq N \leq 2×10^5$
• $1 \leq Q \leq 2×10^5$
• $1 \leq A_i, X \leq 10^9$
• $c \in \{1, 2\}$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで $query_i$ は $i$ 番目のクエリを意味する。

$N\ Q$
$A_1\ A_2\ ...\ A_N$
$query_1$
$query_2$
$:$
$query_Q$

各クエリは以下の形式で与えられる。

$c\ X$ 

出力

$Q$ 行出力せよ。

$i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。

サンプル

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

2
3
-1
5