Chunky Munky has an array of ~N~ numbers ~a_1, a_2, \dots, a_N~, along with ~Q~ queries.

Each query is one of the following ~2~ types:

• 1 p x: Set ~a_p = x~.
• 2 l r k: Chunky Munky picks up ~a_l~, then ~a_{l+1}, a_{l+2}, \dots~ all the way until ~a_r~, and would like to know the index of the first element he picks up with a value strictly less than ~k~. It's guaranteed that the value of ~k~ will always be such that he will pick up a value strictly less than ~k~ during the process.

Help Chunky Munky answer his queries!

Note that this problem will be online enforced, meaning that input will be given in an encrypted format. To encrypt the data, the values ~p, x, l, r, k~ in queries will be given as ~p \oplus \text{lastAns}, x \oplus \text{lastAns}, l \oplus \text{lastAns}, r \oplus \text{lastAns}, k \oplus \text{lastAns}~, where ~\oplus~ denotes the bitwise XOR operation. Note that ~\text{lastAns}~ at any time is defined as the answer to the latest type ~2~ query. If no type ~2~ queries have occurred so far, ~\text{lastAns} = 0~.

Constraints

For all subtasks:

~1 \le N, Q \le 10^6~

~1 \le a_i, x, k \le 10^9~

~1 \le p \le N~

~1 \le l \le r \le N~

For ~3~ of ~20~ points, ~1 \le N, Q \le 2\,000~.

For ~10~ of ~20~ points, ~1 \le N, Q \le 100\,000~.

For all ~20~ points, no additional constraints apply.

Input Specification

The first line contains the integers ~N~ and ~Q~.

The second line contains the array ~a_1, a_2, \dots, a_N~.

The next ~Q~ lines each contain a query of one of the above types.

Output Specification

For each query of type ~2~, output its answer on a separate line.

Sample Input

10 5
3 1 4 1 5 9 2 6 5 3
2 6 10 6
2 2 14 1
2 6 2 6
1 0 14
2 7 3 7

Sample Input (Unencrypted)

10 5
3 1 4 1 5 9 2 6 5 3
2 6 10 6
2 5 9 6
2 3 7 3
1 4 10
2 3 7 3

Sample Output

7
5
4
7