問題文

長さ $N$ の配列 $A$ があり、配列 $A$ には $1$ 以上 $M$ 以下の整数 $i$ が $a_i$ 個 あります。

クエリが $Q$ 個与えられるので、順に処理してください。 $i$ 番目のクエリでは $T_i,X_i,Y_i$ が与えれます。

• $T_i=1$ のとき

配列 $A$ に整数 $X_i$ を $Y_i$ 個追加する。

• $T_i=2$ のとき

配列 $A$ から整数 $X_i$ を $Y_i$ 個取り除く。ただし、このとき配列 $A$ に整数 $X_i$ が $Y_i$ 個以上あることが保証される。

• $T_i=3$ のとき

配列 $A$ の最頻値を出力する。ただし、最頻値が複数ある場合はその中で最大の値を出力する。

入力

$N\ M$
$a_1 \ldots a_M$
$Q$
$T_1\ X_1\ Y_1$
$\vdots$
$T_Q\ X_Q\ Y_Q$

• $1$ 行目に $N$ と $M$ が空白区切りで与えられる

• $2$ 行目に $a_i$ が空白区切りで与えられる

• $3$ 行目に $Q$ が与えれられる

• $4\sim Q+3$ 行目に $T_i,X_i,Y_i$ が空白区切りで与えられる

制約

• $1≤N≤5\times 10^{17}$

• $1≤M≤10^5$

• $0≤a_i≤N$

• $\sum_{i=1}^{M}a_i=N$

• $1≤Q≤10^5$

• $1≤T_i≤3$

• $T_i=1$ のとき

• $1≤X_i≤M$

• $1≤Y_i≤10^{12}$

• $T_i=2$ のとき

• $1≤X_i≤M$

• $1≤Y_i≤10^{12}$

• 取り除くとき、配列 $A$ に整数 $X_i$ が $Y_i$ 個以上含まれる

• $T_i=3$ のとき

• $X_i=Y_i=0$ (この $X_i,Y_i$ は問題には使用されない)

• $T_i=3$ のクエリが少なくとも $1$ 個含まれる

• 配列 $A$ が空になるようなテストケースは与えられない

• 入力は全て整数である

出力

$T_i=3$ であるような各クエリについてそれぞれ $1$ 行ずつ出力してください。

最後に改行してください。

サンプル

3 3
1 1 1
10
1 1 5
3 0 0
1 2 8
3 0 0
1 3 2
3 0 0
1 1 10
3 0 0
1 2 7
3 0 0

1
2
2
1
2

25 3
10 10 5
16
3 0 0
1 3 4
2 1 1
3 0 0
2 2 1
3 0 0
1 2 1
3 0 0
1 1 2
3 0 0
1 2 3
3 0 0
2 1 5
3 0 0
2 2 5
3 0 0

2
2
3
2
1
2
2
3

1000000000000 2
500000000000 500000000000
3
2 2 500000000000
2 1 499999999999
3 0 0

1