Image Link : In case image is not visible ( Link )

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 = 2 ⁽ⁿ⁾ ; 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 minimun 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 <= 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