题目背景

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

题目描述

给定一个长度为 $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$		无	$8$	无
$2$	$2.5\times 10^5$	$10^5$	A	$4$
$3$			B	$7$
$4$			CD	$13$
$5$			DE	$12$
$6$			D	$16$	$5$
$7$			E	$11$
$8$			无	$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$。