Persistent Range Query

問題文

$N$ 要素の非負整数の集合 $S_{-1}:= \{a_0, a_1 ... a_{N-2}, a_{N-1} \}$ が与えられます.

以下の $3$ 種類のクエリを $Q$ 回処理してください. $i$ 個目のクエリ$(0 \leq i \lt Q)$は以下の形式で与えられます.

• $0$ $t_i$ $x_i$ $:$ $S_{t_i}$ に $x_i$ を追加した集合を $S_i$ とする. $S_{t_i}$ が $x_i$ を含む場合 $S_i := S_{t_i}$ とする
• $1$ $t_i$ $x_i$ $:$ $S_{t_i}$ から $x_i$ を削除した集合を $S_i$ とする. $S_{t_i}$ が $x_i$ を含まない場合 $S_i := S_{t_i}$ とする
• $2$ $t_i$ $l_i$ $r_i$ $:$ $S_{t_i}$ の $l_i$ 以上 $r_i$ 未満の要素の数を答える

注: 基本的に添字が $0$ から始まります

制約

• $1 \leq N, Q \leq 10^5$
• $0 \leq a_i \leq 10^9$
• $a_0, a_1 ... a_{N-2}, a_{N-1}$ は相異なる
• $-1 \leq t_i \lt i$
• $0 \leq x_i, l_i, r_i - 1 \leq 10^9$

入力

入力はすべて整数である。

N Q
a_0 a_1 ....     a_{N-2} a_{N-1}
query 0
query 1
.
.
.
query Q-1

出力

タイプ2のクエリに対する答えを1行ずつ出力してください.

サンプル

10 10
7 4 3 10 6 8 9 2 1 11
0 -1 16
2 0 17 19
2 -1 9 18
0 -1 8
1 0 3
2 0 1 8
2 -1 15 18
2 -1 0 18
2 3 1 16
0 3 20

0
3
6
0
10
10

10 10
1 13 5 17 4 18 9 8 11 12
0 -1 15
1 -1 2
2 0 3 5
0 1 8
0 -1 1
1 -1 17
2 3 4 13
1 0 9
1 7 18
0 7 6

1
6