给定一个长度为 n 的序列 a1,a2,⋯,an。你需要进行共 q 次下面两种操作:
1 l r
:将 a[l,r] 替换为它的异或差分。形式化地说,对于每个 l<i≤r ,令 bi=aixorai−1 ,然后对于每个 l<i≤r,将 ai 替换为 bi。2 pos
: 查询 apos 的值。
所有操作执行完后,你还需要回答最终的 a 序列。
输入格式
第一行包含一个整数 T,表示该数据满足第 T 个子任务的限制。
第二行包含两个整数 n,q,分别表示序列的长度和操作的个数。
第三行包含 n 个整数 a1,a2,⋯,an。
接下来 q 行,每行若干个数,表示一个操作。若操作为第一种操作,则此行包含三个数 1 l r
。若操作为第二种操作,则此行包含两个数 2 pos
。
输出格式
设共有 q2 个第二种操作,则输出共包含 q2+n 行。
前 q2 行,每行输出一个整数,表示该操作的答案。
接下来 n 行,每行输出一个整数,表示最终的 a 序列。
样例一
input
1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6
output
9
4
12
1
0
5
4
12
0
explanation
初始时 a=[1,1,5,1,9,4] 。
第一个操作要求输出 a5 ,此时 a5=9 ,故输出 9 。
第二个操作要求将 a[2,5] 替换为它的异或差分, a[2,5] 为 [1,5,1,9] ,它的异或差分为 [1,4,4,8] ,故操作执行完后, a 序列变为 [1,1,4,4,8,4]。
第三个操作要求输出 a4 ,此时 a4=4 ,故输出 4 。
第四个操作要求将 a[3,6] 替换为它的异或差分, a[3,6] 为 [4,4,8,4] ,它的异或差分为 [4,0,12,12] ,故操作执行完后, a 序列变为 [1,1,4,0,12,12] 。
第五个操作要求输出 a6 ,此时 a6=12 ,故输出 12 。
第六个操作要求将 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] 。
样例二 - 样例九
见下发文件 2.in
- 9.in
,2.out
- 9.out
。对于第 i+1 个样例,该样例满足子任务 i 的限制且 T=i。
数据范围
对于所有数据,保证 1≤n≤2.5×105,1≤q≤105,0≤ai<230,1≤l≤r≤n,1≤pos≤n 。
子任务编号 | n≤ | q≤ | 特殊性质 | 分值 | 子任务依赖 |
---|---|---|---|---|---|
1 | 2×103 | 2×103 | 无 | 8 | 无 |
2 | 2.5×105 | 105 | A | 4 | |
3 | B | 7 | |||
4 | CD | 13 | |||
5 | DE | 12 | |||
6 | D | 16 | 5 | ||
7 | E | 11 | |||
8 | 无 | 29 | 1∼7 |
特殊性质 A:∀i≥2,ai=0 。
特殊性质 B:0≤ai≤1 。
特殊性质 C:记序列 a 中非零位置个数为 c ,则 c≤100 。
特殊性质 D:操作 1 满足 l=1,r=n。
特殊性质 E:没有操作 2 。