题目描述

小 $\sigma$ 给了你一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。小 $\sigma$ 需要你执行共 $q$ 次下面两种操作：

1. 1 l r：将 $a[l,r]$ 替换为它的异或差分。形式化地说，对于每个 $l<i\le r$，令

   $$b_i=a_i\operatorname{xor} a_{i-1},$$

   然后对于每个 $l<i\le r$，将 $a_i$ 替换为 $b_i$。其中 $a_l$ 保持不变。

2. 2 pos：查询 $a_{pos}$ 的值。

所有操作执行完后，你还需要回答最终的 $a$ 序列。

输入格式

第一行包含一个整数 $T$，表示该数据满足第 $T$ 个子任务的限制。

第二行包含两个整数 $n,q$，分别表示序列长度和操作个数。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行若干个数，表示一个操作：

• 若操作为第一种操作，则此行包含三个整数 1 l r；
• 若操作为第二种操作，则此行包含两个整数 2 pos。

输出格式

设共有 $q_2$ 个第二种操作，则输出共包含 $q_2+n$ 行。

前 $q_2$ 行，每行输出一个整数，表示对应查询操作的答案。

接下来 $n$ 行，每行输出一个整数，表示最终的 $a$ 序列。

样例 0

输入

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

解释

初始时：

$$a=[1,1,5,1,9,4]。$$

第 $1$ 个操作查询 $a_5$ 的值，此时 $a_5=9$，输出 $9$。

第 $2$ 个操作要求将 $a[2,5]$ 替换为它的异或差分。$a[2,5]$ 为 $[1,5,1,9]$，它的异或差分为 $[1,4,4,8]$，故操作执行完后：

$$a=[1,1,4,4,8,4]。$$

第 $3$ 个操作查询 $a_4$ 的值，此时 $a_4=4$，输出 $4$。

第 $4$ 个操作要求将 $a[3,6]$ 替换为它的异或差分。$a[3,6]$ 为 $[4,4,8,4]$，它的异或差分为 $[4,0,12,12]$，故操作执行完后：

$$a=[1,1,4,0,12,12]。$$

第 $5$ 个操作查询 $a_6$ 的值，此时 $a_6=12$，输出 $12$。

第 $6$ 个操作要求将 $a[1,6]$ 替换为它的异或差分。$a[1,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\le n\le 2.5\times 10^5, \quad 1\le q\le 10^5, \quad 0\le a_i<2^{30}, \quad 1\le l\le r\le n, \quad 1\le pos\le n。$$

子任务编号	子任务分值	$n\le$	$q\le$	特殊性质
1	10	$2\times 10^3$		无
2		$2.5\times 10^5$	$10^5$	A
3				B
4				CD
5				DE
6				D
7				E
8	30			无

特殊性质：

• A：$\forall i\ge 2,\ a_i=0$。
• B：$0\le a_i\le 1$。
• C：记序列 $a$ 中非零位置个数为 $c$，则 $c\le 100$。
• D：操作 1 满足 $l=1,r=n$。
• E：没有操作 2。