Yugu Xiaoyu gives you a sequence of length $n$. A sub-interval of the interval $[l, r]$ is defined as any interval $[l', r']$ such that $l', r'$ are integers and $l \le l' \le r' \le r$.

There are $m$ operations:

1 x y: Change the value at position $x$ to $y$.

2 l r x: Query how many sub-intervals of the interval $[l, r]$ have a maximum value less than or equal to $x$.

Input

The first line contains two integers $n$ and $m$. The second line contains $n$ integers representing the sequence.

The next $m$ lines each contain an operation in the format 1 x y or 2 l r x.

Output

For each type 2 operation, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

1
1
7
0

Subtasks

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

For $100\%$ of the data, $n, m \le 3 \times 10^5$, $1 \le l \le r \le n$, $1 \le x, y \le n$. Each element in the sequence is in the range $[1, n]$, and all numbers are integers.