You are given an array \(A\) consisting of \(N\) positive integers. You are required to support \(Q\) queries of the following two forms:

• 1 x y: Change the element at the one-indexed position \(x\) to \(y\).
• 2 x y: Output the number of integers in the array that are greater than or equal to \(x\) and less than or equal to \(y\).

Can you solve it?

Input

The first line will contain two space separated integers, \(N\) and \(Q\), indicating the number of elements in the array and the number of queries, respectively.

The second line will contain \(N\) space separated integers, representing the elements of \(A\).

The next \(Q\) lines will contain three space separated integers, representing the queries you are to perform.

Output

For each query of the second type, output the answer on its own line.

Subtasks

For all subtasks,

\(1 \le A_{i} \le 10^{9}\)

At any point in time, the maximum element in the array will not surpass \(10^{9}\).

It is guaranteed that for all queries of the second type, \(x \le y\) will be true.

Subtask 1 [30%]

\(1 \le N, Q \le 10^{3}\)

Subtask 2 [70%]

\(1 \le N, Q \le 3\times10^{4}\)

Sample Input 1

5 3
1 7 6 9 20
1 1 5
1 2 4
2 6 15

Sample Output 1

2

Explanation for Sample Output 1

After the first \(2\) queries, the array becomes \(\{5,4,6,9,20\}\). There are \(2\) elements greater than or equal to \(6\) and less than or equal to \(15\), which are \(6\) and \(9\). So, we output \(2\).