Background

Please note: this problem is not a segment tree template problem.

Problem Description

You are 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\sim r}$ with its XOR difference. Formally, let $b_i := a_i \text{ xor } a_{i-1}$ ($l<i\leq r$), and 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 Format

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

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

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

In the next $q$ lines, each line contains several numbers describing one operation. If it is the first type of operation, the line contains three numbers 1 l r. If it is the second type of operation, the line contains two numbers 2 pos.

Output Format

Suppose there are $q_2$ operations of the second type. Output a total of $q_2+n$ lines.

In the first $q_2$ lines, output one integer per line, which is the answer to that query.

In the next $n$ lines, output one integer per line, which is the final sequence $a$.

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

9
4
12
1
0
5
4
12
0

Hint

More samples can be found in the attached file. For the $(i + 1)$-th sample, $T = i$.

Sample 1 Explanation

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

The first operation asks to output $a_5$. At this time, $a_5=9$, so output $9$.

The second operation asks to replace $a_{2\sim 5}$ with its XOR difference. $a_{2\sim 5}$ is $[1,5,1,9]$, and its XOR difference is $[1,4,4,8]$. Therefore, after this operation, the sequence $a$ becomes $[1,1,4,4,8,4]$.

The third operation asks to output $a_4$. At this time, $a_4=4$, so output $4$.

The fourth operation asks to replace $a_{3\sim 6}$ with its XOR difference. $a_{3\sim 6}$ is $[4,4,8,4]$, and its XOR difference is $[4,0,12,12]$. Therefore, after this operation, the sequence $a$ becomes $[1,1,4,0,12,12]$.

The fifth operation asks to output $a_6$. At this time, $a_6=12$, so output $12$.

The sixth operation asks to replace $a_{1\sim 6}$ with its XOR difference. $a_{1\sim 6}$ is $[1,1,4,0,12,12]$, and its XOR difference is $[1,0,5,4,12,0]$. Therefore, after this operation, the sequence $a$ becomes $[1,0,5,4,12,0]$.

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

Constraints and Notes

For all testdata, 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 the sequence $a$. Then $c\leq 100$.

Special Property D: For operation $1$, it holds that $l=1$ and $r=n$.

Special Property E: There is no operation $2$.

Translated by ChatGPT 5