There is an integer sequence aa of length nn and there are two kinds of operations:
0 l r: select some numbers from al...aral...ar so that their xor sum is maximum, and print the maximum value.
1 x: append xx to the end of the sequence and let n=n+1n=n+1.
Input
There are multiple test cases. The first line of input contains an integer T(T≤10)T(T≤10), indicating the number of test cases. For each test case: The first line contains two integers n,m(1≤n≤5×105,1≤m≤5×105)n,m(1≤n≤5×105,1≤m≤5×105), the number of integers initially in the sequence and the number of operations. The second line contains nn integers a1,a2,...,an(0≤ai<230)a1,a2,...,an(0≤ai<230), denoting the initial sequence. Each of the next mm lines contains one of the operations given above. It's guaranteed that ∑n≤106,∑m≤106,0≤x<230∑n≤106,∑m≤106,0≤x<230. And operations will be encrypted. You need to decode the operations as follows, where lastans denotes the answer to the last type 0 operation and is initially zero: For every type 0 operation, let l=(l xor lastans)mod n + 1, r=(r xor lastans)mod n + 1, and then swap(l, r) if l>r. For every type 1 operation, let x=x xor lastans.
Output
For each type 0 operation, please output the maximum xor sum in a single line.