区間と最頻値

注意

Pythonはpypyを使ってください

問題

長さ $N$ の数列 $A$ が与えられます。 $Q$ 回のクエリが与えられるので順に処理してください。

• 1 L R: $A_L, \ldots, A_R$ 内での最頻値のうち最小の値を出力する
• 2 k X: $A_k$に$X$を代入する

最頻値は、その区間で最も多く出現する数値です。

制約

• $1 \leqq N \leqq 10^6$
• $1 \leqq A_i, X \leqq 10^3$
• $1 \leqq Q \leqq 3 \times 10^3$
• $1 \leqq L \leqq R \leqq N$
• $1 \leqq k \leqq N$

入力

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

出力

各タイプ１のクエリに対して答えを１行で出力してください。

入力例１

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

出力例１

4
1
1

１つめのクエリの部分配列は$(1, 4, 4)$なので$4$が最頻値です。

２つめのクエリの部分配列は$(1, 4, 4, 1)$で$1,4$が同数ありますが、小さい方の$1$が答えです。

３つめのクエリで数列$A$は$(1, 1, 4, 1, 3)$となります。

最後は部分配列$(1, 1, 4)$なので$1$が最頻値となります。

入力例２

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

出力例２

3
1
10
4