Bob is playing with an array!

Having studied the Fenwick Tree recently, Bob is curious whether he'd be able to solve the following types of operations to the array:

• Q1 i j: Calculate and output the sum of the subarray between the indices \(i\) and \(j\) \((1 \le i \le j \le N)\) inclusive.
• Q2 L R: Count and output the number of elements in the array with values in between \(L\) and \(R\) \((0 \le L \le R \le 10^5)\) inclusive.
• U i v: Change the value of the \(i\)-th element \((1 \le i \le N)\) in the array to \(v\) \((0 \le v \le 10^5)\).

Unfortunately, Bob needs a little bit of help. Can you do it for him instead?

Input Specification

The first line contains two integers \(N\) and \(Q\) \((1 \le N, Q \le 10^5)\), the size of the array and the number of operations to the array.
The second line contains \(N\) nonnegative integers, each separated by a space. The value of these elements are nonnegative and will never exceed \(10^5\).
The next \(Q\) lines each contain an operation to be performed on the array.

The values inside the array will always be between \(0\) and \(10^5\) inclusive.

Output Specification

On a new line, output an integer for every Q1 and Q2 query representing the answer to the respective queries.

Sample Input

5 2
3 1 0 5 2
Q1 1 3
Q2 2 4

Sample Output

4
2

Explanation of Output

The sum of the subarray can be described as \(3 + 1 + 0 = 4\) (These are the first three elements in the array).

Overall, there are \(2\) elements that fall in the range \([2, 4]\), which are the first and last elements in the array.