問題文

NN 個の色のついた花が左右一列に並んでおり、左から ii 番目の花の色は CiC_i です。

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

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

制約

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

入力

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

NNQQ
C1C_1C2C_2   . . .   CNC_N
query 11
query 22
\vdots

query QQ

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

11kkxx

22llrrxx

出力

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

入出力例

入力例1
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
出力例1
2
3
2
1

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

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

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

Submit


Go (1.21)