分数: 600 点
问题陈述
对于非负整数序列 (a _ 1,a _ 2,\ldots,a _ n),让我们定义它 \operatorname{xor} 作为整数 X 这样,对于所有非负整数 j:
- 这 2^j的地点 X is 1 当且仅当其中有奇数个元素 a _ 1,\ldots,a _ n 谁的 2^j的位置是 1.
给你一个非负整数序列 A=(A _ 1,A _ 2,\ldots,A _ N) 长度 N.
让 \lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k) 是所有非负整数的集合,可以是 \operatorname{xor} 的不一定连续(可能为空)的子序列 A.
给定整数 L 和 R,打印 s _ L,s _ {L+1},\ldots,s _ R 按此顺序。
约束
- 1\leq N\leq2\times10^5
- 0\leq A _ i\lt2^{60}\ (1\leq i\leq N)
- 1\leq L\leq R\leq k
- R-L\leq2\times10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N L R A _ 1 A _ 2 \ldots A _ N
输出
打印 s _ i\ (L\leq i\leq R) 按升序排列 i,用空格分隔。
示例输入 1
4 1 8 2 21 17 21
示例输出 1
0 2 4 6 17 19 21 23
有 14 不一定连续的子序列 A: (),(2),(17),(21),(2,17),(2,21),(17,21),(21,17),(21,21),(2,17,21),(2,21,17),(2,21,21),(21,17,21),和 (2,21,17,21), 谁的 \operatorname{xor}如下。
- 的 \operatorname{xor} of () is 0.
- 的 \operatorname{xor} of (2) is 2.
- 的 \operatorname{xor} of (17) is 17.
- 的 \operatorname{xor} of (21) is 21.
- 的 \operatorname{xor} of (2,17) is 19.
- 的 \operatorname{xor} of (2,21) is 23.
- 的 \operatorname{xor} of (17,21) is 4.
- 的 \operatorname{xor} of (21,17) is 4.
- 的 \operatorname{xor} of (21,21) is 0.
- 的 \operatorname{xor} of (2,17,21) is 6.
- 的 \operatorname{xor} of (2,21,17) is 6.
- 的 \operatorname{xor} of (2,21,21) is 2.
- 的 \operatorname{xor} of (21,17,21) is 17.
- 的 \operatorname{xor} of (2,21,17,21) is 19.
因此,可以作为的所有非负整数的集合 \operatorname{xor} 的子序列 A is \lbrace0,2,4,6,17,19,21,23\rbrace.
示例输入 2
4 3 7 2 21 17 21
示例输出 2
4 6 17 19 21
示例输入 3
5 1 1 0 0 0 0 0
示例输出 3
0
A 可能包含相同的值。
示例输入 4
6 21 21 88 44 82 110 121 80
示例输出 4
41
示例输入 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
示例输出 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
请注意,输入和输出可能不适合 32-\operatorname{bit} 整数类型。