[集训队互测 2022] 线段树

请注意：**本题不是线段树模板题**。

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots a_n$。你需要进行共 $q$ 次下面两种操作： - `1 l r`：将 $a_{l\sim r}$ 替换为它的异或差分。形式化地说，令 $b_i := a_i \text{ xor } a_{i-1}$（$l<i\leq r$），然后对于每个 $l<i\leq r$，将 $a_i$ 替换为 $b_i$。 - `2 pos`：查询 $a_{pos}$ 的值。 操作执行完后，你还需要回答最终的 $a$ 序列。

第一行包含一个整数 $T$，表示该数据满足第 $T$ 个子任务的限制。 第二行包含两个整数 $n,q$，分别表示序列的长度和操作的个数。 第三行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。 接下来 $q$ 行，每行若干个数，表示一个操作。若操作为第一种操作，则此行包含三个数 `1 l r` 。若操作为第二种操作，则此行包含两个数 `2 pos`。

设共有 $q_2$ 个第二种操作，则输出共包含 $q_2+n$ 行。 前 $q_2$ 行，每行输出一个整数，表示该操作的答案。 接下来 $n$ 行，每行输出一个整数，表示最终的 $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

**更多样例见下发文件**。对于第 $i + 1$ 个样例，$T = i$。 ### 样例 1 解释 初始时 $a=[1,1,5,1,9,4]$。 第一个操作要求输出 $a_5$，此时 $a_5=9$，故输出 $9$。 第二个操作要求将 $a_{2\sim 5}$ 替换为它的异或差分，$a_{2\sim 5}$ 为 $[1,5,1,9]$，它的异或差分为 $[1,4,4,8]$，故操作执行完后，$a$ 序列变为 $[1,1,4,4,8,4]$ 。 第三个操作要求输出 $a_4$，此时 $a_4=4$，故输出 $4$。 第四个操作要求将 $a_{3\sim 6}$ 替换为它的异或差分， $a_{3\sim 6}$ 为 $[4,4,8,4]$，它的异或差分为 $[4,0,12,12]$，故操作执行完后， $a$ 序列变为 $[1,1,4,0,12,12]$。 第五个操作要求输出 $a_6$，此时 $a_6=12$，故输出 $12$。 第六个操作要求将 $a_{1\sim 6}$ 替换为它的异或差分， $a_{1\sim 6}$ 为 $[1,1,4,0,12,12]$，它的异或差分为 $[1,0,5,4,12,0]$，故操作执行完后，$a$ 序列变为 $[1,0,5,4,12,0]$。 最终的 $a$ 序列为 $[1,0,5,4,12,0]$。 ### 数据范围与约定 对于所有数据，保证 $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$，$1\leq pos\leq n$。 | 子任务编号 | $n\leq$ | $q\leq$ | 特殊性质 | 分值 | 子任务依赖 | | :--------: | :--------------: | :------------: | :------: | :--: | :-------------: | | $1$ | $2\times 10^3$ | $2\times 10^3$ | 无 | $8$ | 无 | | $2$ | $2.5\times 10^5$ | $10^5$ | A | $4$ | 无 | | $3$ | $2.5\times 10^5$ | $10^5$ | B | $7$ | 无 | | $4$ | $2.5\times 10^5$ | $10^5$ | CD | $13$ | 无 | | $5$ | $2.5\times 10^5$ | $10^5$ | DE | $12$ | 无 | | $6$ | $2.5\times 10^5$ | $10^5$ | D | $16$ | $5$ | | $7$ | $2.5\times 10^5$ | $10^5$ | E | $11$ | $5$ | | $8$ | $2.5\times 10^5$ | $10^5$ | 无 | $29$ | $1,2,3,4,5,6,7$ | 特殊性质 A：$\forall i\geq 2, a_i=0$。 特殊性质 B：$0\leq a_i\leq 1$。 特殊性质 C：记序列 $a$ 中非零位置个数为 $c$，则 $c\leq 100$。 特殊性质 D：操作 $1$ 满足 $l=1$，$r=n$。 特殊性质 E：没有操作 $2$。