You are given a 1indexed array A, of length n, and q queries to be performed on it. The queries are of two types

• 1 i x : Change the value of $A_i$ to x
• 2 L R I J : Find l, $r, i$ and j according to the code below. Consider the subarray $B = [A_l, A_{l+1} \ldots A_r]$ . Sort B, and find the Bitwise xor of $B_i, B_{i+1} \ldots B_j$ in the sorted array B.

You maintain the answer to the last query of type 2 in variable ans . Note that ans is initially 0. Now, whenever you get a query of type 2, calculate l, $r, i$ and j as :

l = 1 + ((ans ^ L) % n);
r = 1 + ((ans ^ R) % n);
if(l > r) swap(l, r);
i = 1 + ((I ^ ans) % (r - l + 1));
j = 1 + ((J ^ ans) % (r - l + 1));
if(i > j) swap(i, j);

Note that array A is NOT changed in a query of second type.

Input

• The first line contains n and q
• The next line contains n space separated integers representing the array A
• Each of the next q lines contain a query either of type 1 or type 2 .

Output
For each of the query of type 2, print the required value on a new line.

Constraints

• $1 \le n,q, L, R, I, J \le 5 \times 10^4$

• $1 \le A_i, x \le 10^5$

• At any instant, all elements of A are distinct