問題

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

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

制約

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

入力

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

入力

NNQQ
A1A_1\ldotsANA_N
query1\mathrm{query}_1
\vdots
queryQ\mathrm{query}_Q

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

11iixx

22xx

出力

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

サンプル

入力
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)A = (9, 9, 8, 2, 4, 4, 3, 5, 3) です。

11 番目のクエリについて、 Aj=8A_j = 8 を満たす jj33 です。
22 番目のクエリについて、 Aj=7A_j = 7 を満たす jj は存在しません。
33 番目のクエリについて、 Aj=9A_j = 9 を満たす jj11 です。 A2=9A_2 = 9 も成り立つため、 22 を出力しても構いません。
44 番目のクエリについて、 A7A_788 に変更します。AA(9,9,8,2,4,4,8,5,3)(9, 9, 8, 2, 4, 4, 8, 5, 3) になります。
55 番目のクエリについて、 Aj=8A_j = 8 を満たす jj77 です。A3=8A_3 = 8 も成り立つため、 33 を出力しても構いません。

Submit


Go (1.21)