配点 : $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}$ 演算を表します．

制約

• $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$ に対する答えを空白区切りで出力せよ．

3 2
2 1 3

0 1

操作の度に $A$ は以下のように変化します．

• 初期状態：$A=(2,1,3)$
• $1$ 回目の操作後：$A=(2,3,0)$
• $2$ 回目の操作後：$A=(2,1,1)$

10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404