当前没有测试数据。

G - 部分的XOR枚举

得分 : $600$ 点

问题描述

对于一个非负整数序列 $(a _ 1,a _ 2,\ldots,a _ n)$，我们定义它的 $\operatorname{xor}$ 为整数 $X$，满足对于所有非负整数 $j$：

• 如果在 $a _ 1,\ldots,a _ n$ 中有奇数个元素的 $2^j$ 位是 $1$，则 $X$ 的 $2^j$ 位是 $1$。

给定一个长度为 $N$ 的非负整数序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$。

设 $\lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k)$ 是所有可以成为 $A$ 的一个不一定连续（可能为空）子序列的 $\operatorname{xor}$ 的集合。

给定整数 $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$

输出

按 $i$ 值递增顺序，用空格分隔输出 $s _ i\ (L\leq i\leq R)$。

---

4 1 8
2 21 17 21

0 2 4 6 17 19 21 23

对于 $A$，有 $14$ 个不一定连续的子序列：$(),(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}$ 是 $0$。
• $(2)$ 的 $\operatorname{xor}$ 是 $2$。
• $(17)$ 的 $\operatorname{xor}$ 是 $17$。
• $(21)$ 的 $\operatorname{xor}$ 是 $21$。
• $(2,17)$ 的 $\operatorname{xor}$ 是 $19$。
• $(2,21)$ 的 $\operatorname{xor}$ 是 $23$。
• $(17,21)$ 的 $\operatorname{xor}$ 是 $4$。
• $(21,17)$ 的 $\operatorname{xor}$ 是 $4$。
• $(21,21)$ 的 $\operatorname{xor}$ 是 $0$。
• $(2,17,21)$ 的 $\operatorname{xor}$ 是 $6$。
• $(2,21,17)$ 的 $\operatorname{xor}$ 是 $6$。
• $(2,21,21)$ 的 $\operatorname{xor}$ 是 $2$。
• $(21,17,21)$ 的 $\operatorname{xor}$ 是 $17$。
• $(2,21,17,21)$ 的 $\operatorname{xor}$ 是 $19$。

因此，所有可以成为 $A$ 的子序列的 $\operatorname{xor}$ 的集合是 $\lbrace0,2,4,6,17,19,21,23\rbrace$。

---

4 3 7
2 21 17 21

4 6 17 19 21

---

5 1 1
0 0 0 0 0

0

$A$ 可能包含相同的值。

---

6 21 21
88 44 82 110 121 80

41

---

12 26 48
19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130

13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402

请注意，输入和输出可能不能适应 $32$ 位整数类型。