{"raw_statement":[{"iden":"background","content":"请注意：**本题不是线段树模板题**。"},{"iden":"statement","content":"给定一个长度为 $n$ 的序列 $a_1,a_2,\\cdots a_n$。你需要进行共 $q$ 次下面两种操作：\n\n- `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$。\n\n- `2 pos`：查询 $a_{pos}$ 的值。\n\n操作执行完后，你还需要回答最终的 $a$ 序列。"},{"iden":"input","content":"第一行包含一个整数 $T$，表示该数据满足第 $T$ 个子任务的限制。\n\n第二行包含两个整数 $n,q$，分别表示序列的长度和操作的个数。\n\n第三行包含 $n$ 个整数 $a_1,a_2,\\cdots,a_n$。\n\n接下来 $q$ 行，每行若干个数，表示一个操作。若操作为第一种操作，则此行包含三个数 `1 l r` 。若操作为第二种操作，则此行包含两个数 `2 pos`。"},{"iden":"output","content":"设共有 $q_2$ 个第二种操作，则输出共包含 $q_2+n$ 行。\n\n前 $q_2$ 行，每行输出一个整数，表示该操作的答案。\n\n接下来 $n$ 行，每行输出一个整数，表示最终的 $a$\n 序列。"},{"iden":"note","content":"**更多样例见下发文件**。对于第 $i + 1$ 个样例，$T = i$。\n\n### 样例 1 解释\n\n初始时 $a=[1,1,5,1,9,4]$。\n\n第一个操作要求输出 $a_5$，此时 $a_5=9$，故输出 $9$。\n\n第二个操作要求将 $a_{2\\sim 5}$ 替换为它的异或差分，$a_{2\\sim 5}$ 为 $[1,5,1,9]$，它的异或差分为 $[1,4,4,8]$，故操作执行完后，$a$ 序列变为 $[1,1,4,4,8,4]$\n。\n\n第三个操作要求输出 $a_4$，此时 $a_4=4$，故输出 $4$。\n\n第四个操作要求将 $a_{3\\sim 6}$ 替换为它的异或差分， $a_{3\\sim 6}$ 为 $[4,4,8,4]$，它的异或差分为 $[4,0,12,12]$，故操作执行完后， $a$ 序列变为 $[1,1,4,0,12,12]$。\n\n第五个操作要求输出 $a_6$，此时 $a_6=12$，故输出 $12$。\n\n第六个操作要求将 $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]$。\n\n最终的 $a$ 序列为 $[1,0,5,4,12,0]$。\n\n### 数据范围与约定\n\n对于所有数据，保证 $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\n| 子任务编号 |     $n\\leq$      |    $q\\leq$     | 特殊性质 | 分值 |   子任务依赖    |\n| :--------: | :--------------: | :------------: | :------: | :--: | :-------------: |\n|    $1$     |  $2\\times 10^3$  | $2\\times 10^3$ |    无    | $8$  |       无        |\n|    $2$     | $2.5\\times 10^5$ |     $10^5$     |    A     | $4$  |       无        |\n|    $3$     | $2.5\\times 10^5$ |     $10^5$     |    B     | $7$  |       无        |\n|    $4$     | $2.5\\times 10^5$ |     $10^5$     |    CD    | $13$ |       无        |\n|    $5$     | $2.5\\times 10^5$ |     $10^5$     |    DE    | $12$ |       无        |\n|    $6$     | $2.5\\times 10^5$ |     $10^5$     |    D     | $16$ |       $5$       |\n|    $7$     | $2.5\\times 10^5$ |     $10^5$     |    E     | $11$ |       $5$       |\n|    $8$     | $2.5\\times 10^5$ |     $10^5$     |    无    | $29$ | $1,2,3,4,5,6,7$ |\n\n特殊性质 A：$\\forall i\\geq 2, a_i=0$。\n\n特殊性质 B：$0\\leq a_i\\leq 1$。\n\n特殊性质 C：记序列 $a$ 中非零位置个数为 $c$，则 $c\\leq 100$。\n\n特殊性质 D：操作 $1$ 满足 $l=1$，$r=n$。\n\n特殊性质 E：没有操作 $2$。\n"}],"translated_statement":null,"sample_group":[["1\n6 6\n1 1 5 1 9 4\n2 5\n1 2 5\n2 4\n1 3 6\n2 6\n1 1 6","9\n4\n12\n1\n0\n5\n4\n12\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}