Binary Representation of a number represents a point (vertex) in the N-th dimensional hyper-cube (N is the number of bits used to represent the number in binary form). Eg. point 3 (011) and 5 (101) are shown in 3-dimensional cube in the figure. As the value of points increases, number of axes to represent it in the hyper-cube increases.

Given an N-th dimensional hyper-cube and an array (of size n) of selected points from the cube. We select its complementary point from the cube. We call communication between these points "GOOD" if the distance between given point and its complementary point is maximum. Distance between two points is defined as the bitwise XOR of two points. Let this complementary point be M. The cost of building communication between them is given by

      Cost = 2n; where n is position of unset bit which is at farthest distance from MSB in M

To decrease the cost we have two operations:

• Type1: ' q l r ' :- we select two positions l and r from the array. Output the point from the array, between the smaller and larger position being selected, which has minimum cost of building the communication. In case there are multiple answers, print the point with minimum value.
• Type2: ' u x y ' :- update the point at index x with value y.

NOTE:- ' l r x ' are according to 1-based indexing (1 <= l, r, x <= n)

Constraints

1 <= T <= 20

1 <= n, q <= 10⁵

1 <= array elements <= 10⁹

Input

First line contains number of test cases. Next line contains n and q representing size of array and number of operations. Next line contains array elements. Next q lines operations of type1 and type2 in the specified format.

Output

Give answer of the required type in new lines.

Example

Input:
1
3 3
2 3 4
q 1 3
u 2 5
q 1 2

Output:
3
5