Linear Search? SP

問題

長さ $N$ の整数列 $A$ が与えられます。
以下で説明されるクエリを与えられる順に $Q$ 個処理してください。
クエリは次の $2$ 種類のうちいずれかです。

1 i x : $A_i$ を $x$ に変更する。
2 x : $A_j = x$ を満たす $j$ を $1$ 個出力する。条件を満たす $j$ が複数存在する場合、どれを出力しても構わない。存在しない場合 -1 を出力すること。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 50000$
• $1 \leq A_j \leq 10^9 \ (1 \leq j \leq N)$
• $1 \leq i \leq N$
• $1 \leq x \leq 10^9$
• 2 x のクエリは少なくとも $1$ 個存在する
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで $\mathrm{query}_k$ は $k$ 番目のクエリである。

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

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

サンプル

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

3
-1
1
7

はじめ、 $A = (9, 9, 8, 2, 4, 4, 3, 5, 3)$ です。

$1$ 番目のクエリについて、 $A_j = 8$ を満たす $j$ は $3$ です。
$2$ 番目のクエリについて、 $A_j = 7$ を満たす $j$ は存在しません。
$3$ 番目のクエリについて、 $A_j = 9$ を満たす $j$ は $1$ です。 $A_2 = 9$ も成り立つため、 $2$ を出力しても構いません。
$4$ 番目のクエリについて、 $A_7$ を $8$ に変更します。$A$ は $(9, 9, 8, 2, 4, 4, 8, 5, 3)$ になります。
$5$ 番目のクエリについて、 $A_j = 8$ を満たす $j$ は $7$ です。$A_3 = 8$ も成り立つため、 $3$ を出力しても構いません。