/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ 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 をこの順に出力してください。
制約
- 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
出力
s _ i\ (L\leq i\leq R) を i の昇順に空白区切りで出力せよ。
入力例 1
4 1 8 2 21 17 21
出力例 1
0 2 4 6 17 19 21 23
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 です。
入力例 2
4 3 7 2 21 17 21
出力例 2
4 6 17 19 21
入力例 3
5 1 1 0 0 0 0 0
出力例 3
0
入力例 4
6 21 21 88 44 82 110 121 80
出力例 4
41
入力例 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
出力例 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
入力や出力が 32\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 600 points
Problem Statement
For a sequence of non-negative integers (a _ 1,a _ 2,\ldots,a _ n), let us define its \operatorname{xor} as the integer X such that, for all non-negative integer j:
- the 2^js place of X is 1 if and only if there is an odd number of elements among a _ 1,\ldots,a _ n whose 2^js place is 1.
You are given a sequence of non-negative integers A=(A _ 1,A _ 2,\ldots,A _ N) of length N.
Let \lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k) be the set of all non-negative integers that can be the \operatorname{xor} of a not-necessarily-contiguous (possibly empty) subsequence of A.
Given integers L and R, print s _ L,s _ {L+1},\ldots,s _ R in this order.
Constraints
- 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
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N L R A _ 1 A _ 2 \ldots A _ N
Output
Print s _ i\ (L\leq i\leq R) in ascending order of i, separated by spaces.
Sample Input 1
4 1 8 2 21 17 21
Sample Output 1
0 2 4 6 17 19 21 23
There are 14 not-necessarily-contiguous subsequences of 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), and (2,21,17,21), whose \operatorname{xor}s are as follows.
- The \operatorname{xor} of () is 0.
- The \operatorname{xor} of (2) is 2.
- The \operatorname{xor} of (17) is 17.
- The \operatorname{xor} of (21) is 21.
- The \operatorname{xor} of (2,17) is 19.
- The \operatorname{xor} of (2,21) is 23.
- The \operatorname{xor} of (17,21) is 4.
- The \operatorname{xor} of (21,17) is 4.
- The \operatorname{xor} of (21,21) is 0.
- The \operatorname{xor} of (2,17,21) is 6.
- The \operatorname{xor} of (2,21,17) is 6.
- The \operatorname{xor} of (2,21,21) is 2.
- The \operatorname{xor} of (21,17,21) is 17.
- The \operatorname{xor} of (2,21,17,21) is 19.
Therefore, the set of all non-negative integers that can be the \operatorname{xor} of a subsequence of A is \lbrace0,2,4,6,17,19,21,23\rbrace.
Sample Input 2
4 3 7 2 21 17 21
Sample Output 2
4 6 17 19 21
Sample Input 3
5 1 1 0 0 0 0 0
Sample Output 3
0
A may contain the same value.
Sample Input 4
6 21 21 88 44 82 110 121 80
Sample Output 4
41
Sample Input 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
Sample Output 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
Note that the input and output may not fit into a 32-\operatorname{bit} integer type.