/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N)，及び整数 M が与えられます．
各 k=1,2,\cdots,M について，以下の操作をちょうど k 回行ったあとの A_N の値を求めてください．
- すべての i (1 \leq i \leq N) について，A_i の値を A_1 \oplus A_2 \oplus \cdots \oplus A_i で置き換える． この置き換えはすべての i に対して同時に行う．
ただしここで，\oplus はビット単位 \mathrm{XOR} 演算を表します．
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 0 \leq A_i < 2^{30}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M A_1 A_2 \cdots A_N
出力
各 k に対する答えを空白区切りで出力せよ．
入力例 1
3 2 2 1 3
出力例 1
0 1
操作の度に A は以下のように変化します．
- 初期状態：A=(2,1,3)
- 1 回目の操作後：A=(2,3,0)
- 2 回目の操作後：A=(2,1,1)
入力例 2
10 12 721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427
出力例 2
716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404
Score : 700 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\cdots,A_N), and an integer M.
For each k=1,2,\cdots,M, find the value of A_N after doing the operation below k times.
- For every i (1 \leq i \leq N), simultaneously, replace the value of A_i with A_1 \oplus A_2 \oplus \cdots \oplus A_i.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 0 \leq A_i < 2^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \cdots A_N
Output
Print the answers for respective values of k, separated by spaces.
Sample Input 1
3 2 2 1 3
Sample Output 1
0 1
Each operation changes A as follows.
- Initially: A=(2,1,3).
- After the first operation: A=(2,3,0).
- After the second operation: A=(2,1,1).
Sample Input 2
10 12 721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427
Sample Output 2
716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404