题目描述

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

对于非负整数序列 $(a_1,a_2,\ldots,a_n)$，其 $\operatorname{xor}$ 定义为：存在一个整数 $X$，使得对于所有非负整数 $j$，满足以下条件：

• 当且仅当 $a_1,\ldots,a_n$ 中，用二进制表示时第 $2^j$ 位为 $1$ 的数的个数为奇数时，$X$ 的第 $2^j$ 位为 $1$。

设非负整数集合 $\lbrace s\_1,s\_2,\ldots,s\_k\rbrace\ (s\_1<s\_2<\cdots<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)$，用空格分隔。

样例 1

输入

4 1 8
2 21 17 21

输出

0 2 4 6 17 19 21 23

样例 2

输入

4 3 7
2 21 17 21

输出

4 6 17 19 21

样例 3

输入

5 1 1
0 0 0 0 0

输出

0

样例 4

输入

6 21 21
88 44 82 110 121 80

输出

41

样例 5

输入

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

说明/提示

数据范围

• $1\leq N\leq2\times10^5$
• $0\leq A_i<2^{60}\ (1\leq i\leq N)$
• $1\leq L\leq R\leq k$
• $R-L\leq2\times10^5$
• 输入均为整数

样例解释 1

$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)$ 共 $14$ 种。它们的 $\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$ 的子序列的按位异或可能得到的值的集合为 $\lbrace0,2,4,6,17,19,21,23\rbrace$。

样例解释 5

请注意，输入或输出的数值可能超出 $32\operatorname{bit}$ 整数范围。

由 ChatGPT 4.1 翻译