問題文

$N$ 個の色のついた花が左右一列に並んでおり、左から $i$ 番目の花の色は $C_i$ です。

$Q$ 個のクエリが与えられるので、順番に処理してください。
クエリは次の $2$ 種類のいずれかです。

• 1 k x : 左から $k$ 番目の花の色を $x$ に染める。
• 2 l r x : 左から $l$ 番目から $r$ 番目までの花の中で、色が $x$ である花の個数を答える。

制約

• $1 \leq N, Q \leq 5 \times 10^4$
• $1 \leq k \leq N$
• $1 \leq l \leq r \leq N$
• $1 \leq x \leq 10^{9}$
• $1 \leq C_i \leq 10^{9}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$i \: (1 \leq i \leq Q)$ 番目の query $i$ では、まずクエリの種類 $t_i$ $(1, 2$ のいずれか$)$ が与えられ、 $t_i = 1$ のときは追加で $k, x$、$t_i = 2$ のときは追加で $l, r, x$ が与えられる。
すなわち、各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

出力

$t_i = 2$ を満たすクエリの個数を $q$ として、$q$ 行出力せよ。
$j \: (1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

入出力例

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

2
3
2
1

$1$ 個目のクエリについて、
花の色の状態は $(1, 4, 2, 2, 3, 5, 4, 1)$ であり、左から $1$ 番目から $5$ 番目までの花の中で、色が $2$ であるような花の個数は $2$ です。

$2$ 個目のクエリについて、
花の色の状態は $(1, 4, 2, 2, 2, 5, 4, 1)$ となります。

$3$ 個目のクエリについて、
花の色の状態は $(1, 4, 2, 2, 2, 5, 4, 1)$ であり、左から $1$ 番目から $5$ 番目までの花の中で、色が $2$ であるような花の個数は $3$ です。