GCOM  GOOD COMMUNICATION
Image Link : In case image is not visible ( Link )
Binary Representation of a number represents a point (vertex) in the Nth dimensional hypercube (N is the number of bits used to represent the number in binary form ) . Eg. point 3(011) and 5(101) are shown in 3dimensional cube in the figure. As the value of points increases, number of axes to represent it in the hypercube increases .
Given an Nth dimensional hypercube 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 ^{(n)} ; 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 1based indexing (1 <= l,r <= n)
Constraints
1 <= T <= 20
1 <= n , q <= 10^{5}
1 <= array elements <= 10^{9}
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
hide comments
mehmetin:
20191231 06:24:43
Optimized cin/cout gets time limit, scanf/printf gets acccepted. 

bdezso:
20191223 09:34:43
@y17prashant


stunner2k18:
20191223 05:09:17
AC in one go!!


y17prashant:
20191220 19:54:31
I have added the image link you can view it from there . 

bdezso:
20191220 18:03:01
Could you check my last submission?


nadstratosfer:
20191220 11:06:44
Please use https://www.spoj.com/uploads/ for images so that their visibility does not depend on 3rd party servers.

Added by:  17 Prashant_Singh 
Date:  20191216 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 