题目描述

長さ $N$ の非負整数列 $A=(A\ _\ 1,A\ _\ 2,\ldots,A\ _\ N)$ が与えられます。

非負整数列 $(a\ _\ 1,a\ _\ 2,\ldots,a\ _\ n)$ の $\operatorname{xor}$ を、すべての非負整数 $j$ について次の条件を満たすような整数 $X$ と定義します。

• $a\ _\ 1,\ldots,a\ _\ n$ のうち二進法で表したとき $2^j$ の位が $1$ であるものが奇数個であるとき、かつそのときに限り $2^j$ の位が $1$ である

非負整数の集合 $ \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)$ を $i$ の昇順に空白区切りで出力せよ。

题目大意

对于一个非负整数序列 $a = (a_1, a_2, \dots, a_n)$，我们定义其的异或是一个非负整数 $X$，使得对于任意非负整数 $j$ 有 $X$ 二进制的第 $j$ 位为 $1$ 当且仅当 $a$ 中有奇数个元素满足二进制的第 $j$ 位为 $1$。

给定一个 $n$ 长度序列 $A = (A_1, A_2, \dots, A_n)$。令 $\{s_1, s_2, \dots, s_k\}\ (s_1 < s_2 < \cdots < s_k)$ 为 $A$ 的所有可空子序列的异或组成的集合。注意子序列不一定连续。

再给定两个整数 $l, r$，请输出 $s_l, s_l + 1,\dots, s_r$。

$1\le n \le 2\times 10^5, \ 0\le A_i < 2^{60},\ 1\le l \le r \le k, \ r - l \le 2\times 10^5$。

4 1 8
2 21 17 21

0 2 4 6 17 19 21 23

4 3 7
2 21 17 21

4 6 17 19 21

5 1 1
0 0 0 0 0

0

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

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 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$ です。

Sample Explanation 5

入力や出力が $32\operatorname{bit}$ 整数に収まらない場合があることに注意してください。