C - Linear Search?

問題

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

1 i x : $A_i$ を $x$ に変更する。
2 x : $A_j = x$ を満たす最小の $j$ を出力する。 (そのような $j$ が存在しない場合 -1 を出力すること。)
3 x : $A_j = x$ を満たす最大の $j$ を出力する。 (そのような $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 または 3 x のクエリは少なくとも $1$ 個存在する
• 入力はすべて整数

入力

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

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

出力

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

サンプル

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

3
3
-1
7

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

$1$ 番目のクエリについて、 $A_j = 8$ を満たす最小の $j$ は $3$ です。
$2$ 番目のクエリについて、 $A_j = 8$ を満たす最大の $j$ は $3$ です。
$3$ 番目のクエリについて、 $A_j = 7$ を満たす $j$ は存在しません。
$4$ 番目のクエリについて、 $A_7$ を $8$ に変更します。$A$ は $(9, 9, 8, 2, 4, 4, 8, 5, 3)$ になります。
$5$ 番目のクエリについて、 $A_j = 8$ を満たす最大の $j$ は $7$ です。