部分异或枚举

题目描述

对于非负整数序列 $(a_1,a_2,\ldots,a_n)$,定义其 $\operatorname{xor}$ 为满足以下条件的整数 $X$:对所有非负整数 $j$,$X$ 的 $2^j$ 位是 1,当且仅当 $a_1,\ldots,a_n$ 中 $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$。

输入格式

输入按以下格式从标准输入给出:

$N$ $L$ $R$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

按升序输出 $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 位整数类型中。

数据范围

• $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$
• 输入中的所有值均为整数。