AT_abc283_g.[ABC283G] Partial Xor Enumeration

给定一个长度为 $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\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 翻译