Problem Description

There is an integer sequence $a$ of length $n$ and there are two kinds of operations:

Input

There are multiple test cases. The first line of input contains an integer $T(T\le 10)$, indicating the number of test cases.
For each test case:
The first line contains two integers $n, m(1\le n\le 5\times 10^5, 1\le m\le 5\times 10^5)$, the number of integers initially in the sequence and the number of operations.
The second line contains $n$ integers $a_1,a_2,...,a_n(0\le a_i< 2^{30})$, denoting the initial sequence.
Each of the next $m$ lines contains one of the operations given above.
It's guaranteed that $\sum n\le 10^6, \sum m\le 10^6 , 0\le x< 2^{30}$.
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.

1
3 3
0 1 2
0 1 1
1 3
0 3 4

1
3