GCOM - GOOD COMMUNICATION

no tags 

 

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 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 ^ (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 ' :- it returns the point 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 
Constraints
1 <= T <= 20
1 <= n , q <= 105
1 <= array elements <= 109
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
 

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 (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 1-based indexing (1 <= l,r <= n) 

 

Constraints

 

1 <= T <= 20

 

1 <= n , q <= 105

 

1 <= array elements <= 109

 

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: 2019-12-31 06:24:43

Optimized cin/cout gets time limit, scanf/printf gets acccepted.

bdezso: 2019-12-23 09:34:43

@y17prashant
Finally ac, but the corner case...
btw i enjoyed solving the problem.

stunner2k18: 2019-12-23 05:09:17

AC in one go!!
good communication, good question :P

y17prashant: 2019-12-20 19:54:31

I have added the image link you can view it from there .

bdezso: 2019-12-20 18:03:01

Could you check my last submission?
Whats wrong with my solution?

nadstratosfer: 2019-12-20 11:06:44

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

BTW. The picture is almost invisible in dark CSS.

Last edit: 2019-12-20 11:08:12

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