Shinku Nikaido gives you a sequence $a$ of length $n$ and $m$ operations:

1. For all elements in the range $[l, r]$ that are greater than $x$, subtract $x$ from them.
2. Query the number of occurrences of $x$ in the range $[l, r]$.

Input

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

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

The next $m$ lines each contain four integers:

• 1 l r x: Subtract $x$ from all numbers in the range $[l, r]$ that are greater than $x$.
• 2 l r x: Query the number of occurrences of $x$ in the range $[l, r]$.

Output

For each query, output a single integer representing the answer.

Examples

Input 1

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

Output 1

3
3
0
3

Subtasks

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

For $100\%$ of the data, $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