Marisa has given you a sequence of length n, with m operations:
1. Decrease by x the numbers greater than x in the interval [l,r].
2. Count the occurrences of x in the interval [l,r].
### Input
The first line contains two integers n,m.
The second line contains n integers representing the sequence a.
The next m lines each contain four integers:
- 1lrx: Decrease by x the numbers greater than x in the interval [l,r].
- 2lrx: Count the occurrences of x in the interval [l,r].
### Output
For each query, output an integer representing the answer.
### Constraints
- 1≤l≤r≤n
- x,n,m,ai≤105
### Example
Input
5615558225512432252225513512151
Output
3303
