G: Freqs

問題

長さ $N$ の数列 $A = (a_1, a_2, ..., a_N)$ が与えられます。以下で説明されるクエリを $Q$ 回処理してください。クエリは $4$ 種類あります。

• クエリ 1: $l, r, x$ が与えられるので、$a_i$ ($l \leq i \leq r$) を $\min(a_i, x)$ に更新する。
• クエリ 2: $l, r, x$ が与えられるので、$a_i$ ($l \leq i \leq r$) を $\max(a_i, x)$ に更新する。
• クエリ 3: $l, r, x$ が与えられるので、$a_i$ ($l \leq i \leq r$) を $a_i + x$ に更新する。
• クエリ 4: $l, r, x, y$ が与えられるので、$l \leq i \leq r$ かつ $x \leq a_i \leq y$ を満たす $i$ の個数を報告する。

入力形式

$N$ $Q$
$a_1$ $a_2$ ... $a_N$
$q_1$
...
$q_Q$

ただし、$q_j$ ($1\leq j \leq Q$) の形式は次のいずれかです。

クエリ 1：

1 $l$ $r$ $x$

クエリ 2：

2 $l$ $r$ $x$

クエリ 3：

3 $l$ $r$ $x$

クエリ 4：

4 $l$ $r$ $x$ $y$

制約

• 入力は全て整数で与えられる
• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $-10^9 \leq a_i \leq 10^9$ ($1 \leq i \leq N$)
• $1 \leq l_i \leq r_i \leq N$ ($1 \leq i \leq Q$)
• クエリ 1, 2, 3 において $-10^9 \leq x_i \leq 10^9$ ($1 \leq i \leq Q$)
• クエリ 4 において $-10^{15} \leq x_i \leq y_i \leq 10^{15}$ ($1 \leq i \leq Q$)

出力形式

各クエリ 4 に対して、その答えを一行ずつ出力してください。

入力例1

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

出力例1

2
2
3
3

$q_1$ のクエリ 4 について、条件を満たす $i$ は $3$ と $5$ なので、その個数 $2$ を出力します。クエリ 1, 2, 3 の更新により、数列 $A$ は次のように変化していきます。

$q_2$ の直後：

3 3 4 3 5 9

$q_3$ の直後：

3 3 4 6 8 12

$q_5$ の直後：

3 3 -6 -4 -2 2

$q_7$ の直後：

1 1 -6 -4 -2 1

入力例2

10 12
1 -1 -3 9 0 1 -3 7 5 -8
1 1 6 4
4 2 10 3 9
2 4 9 7
3 5 8 -2
2 1 3 1
4 8 10 -10 1
3 2 5 3
4 1 3 3 7
1 2 2 5
4 1 9 1 5
1 3 10 2
4 5 7 -2 4

出力例2

3
1
2
6
3

---