Description

Erjiedang Zhenhong gives you a sequence $a$ of length $n$, with $m$ operations.

1. For every number greater than $x$ in the interval $[l,r]$, subtract $x$ from it.
2. Query the number of occurrences of $x$ in the interval $[l,r]$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a$.

Then follow $m$ lines, each containing four integers:

• 1 l r x: For all numbers greater than $x$ in $[l,r]$, subtract $x$.
• 2 l r x: Query the number of occurrences of $x$ in $[l,r]`.

Output Format

For each type-2 query, output one integer representing the answer.

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

3
3
0
3

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 5 \times 10^5$, $1 \le l \le r \le n$, $0 \le a_i, x \le 10^5 + 1$.

By nzhtl1477.

Translated by ChatGPT 5