Given a sequence $a_1, a_2, \cdots, a_n$ of length $n$, you need to perform a total of $q$ operations of the following two types:

• 1 l r: Replace $a[l, r]$ with its XOR difference. Formally, for each $l < i \leq r$, let $b_i = a_i \operatorname{xor} a_{i-1}$, then for each $l < i \leq r$, replace $a_i$ with $b_i$.
• 2 pos: Query the value of $a_{pos}$.

After all operations are completed, you also need to output the final sequence $a$.

Input

The first line contains an integer $T$, representing that the data satisfies the constraints of the $T$-th subtask.

The second line contains two integers $n$ and $q$, representing the length of the sequence and the number of operations, respectively.

The third line contains $n$ integers $a_1, a_2, \cdots, a_n$.

The next $q$ lines each contain several numbers representing an operation. If the operation is of the first type, the line contains three numbers 1 l r. If the operation is of the second type, the line contains two numbers 2 pos.

Output

Let $q_2$ be the number of operations of the second type. The output contains $q_2 + n$ lines.

The first $q_2$ lines each output an integer, representing the answer to the corresponding query.

The next $n$ lines each output an integer, representing the final sequence $a$.

Examples

Input 1

1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6

Output 1

9
4
12
1
0
5
4
12
0

Note 1

Initially, $a = [1, 1, 5, 1, 9, 4]$.

The first operation asks for $a_5$, which is $9$, so output $9$.

The second operation requires replacing $a_{[2, 5]}$ with its XOR difference. $a_{[2, 5]}$ is $[1, 5, 1, 9]$, its XOR difference is $[1, 4, 4, 8]$, so after the operation, the sequence $a$ becomes $[1, 1, 4, 4, 8, 4]$.

The third operation asks for $a_4$, which is $4$, so output $4$.

The fourth operation requires replacing $a_{[3, 6]}$ with its XOR difference. $a_{[3, 6]}$ is $[4, 4, 8, 4]$, its XOR difference is $[4, 0, 12, 12]$, so after the operation, the sequence $a$ becomes $[1, 1, 4, 0, 12, 12]$.

The fifth operation asks for $a_6$, which is $12$, so output $12$.

The sixth operation requires replacing $a_{[1, 6]}$ with its XOR difference. $a_{[1, 6]}$ is $[1, 1, 4, 0, 12, 12]$, its XOR difference is $[1, 0, 5, 4, 12, 0]$, so after the operation, the sequence $a$ becomes $[1, 0, 5, 4, 12, 0]$.

The final sequence $a$ is $[1, 0, 5, 4, 12, 0]$.

Examples 2 - 9

See the provided files 2.in - 9.in and 2.out - 9.out. For the $(i+1)$-th example, the sample satisfies the constraints of subtask $i$ and $T=i$.

Constraints

For all data, it is guaranteed that $1 \leq n \leq 2.5 \times 10^5$, $1 \leq q \leq 10^5$, $0 \leq a_i < 2^{30}$, $1 \leq l \leq r \leq n$, and $1 \leq pos \leq n$.

Special Property A: $\forall i \geq 2, a_i=0$.

Special Property B: $0 \leq a_i \leq 1$.

Special Property C: Let $c$ be the number of non-zero positions in sequence $a$, then $c \leq 100$.

Special Property D: Operation 1 satisfies $l=1, r=n$.

Special Property E: No operation 2.