← 返回题目列表

AtCoder · abc283_g

G. 部分异或枚举

中文机器翻译题面 查看原题

分数: 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} 整数类型。