# [集训队互测 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

### 样例输入 #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
```

### 样例输出 #1

```
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$。