题目描述

長さ $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$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。
一般に $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$ の順番によらないことが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

各 $k$ に対する答えを空白区切りで出力せよ．

题目大意

给定一个长度为 $n$ 的序列 $A$（下标从 $1$ 开始），还有一个整数 $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$。

3 2
2 1 3

0 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

提示

制約

• $1\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ M\ \leq\ 10^6$
• $0\ \leq\ A_i\ <\ 2^{30}$
• 入力される値はすべて整数

Sample Explanation 1

操作の度に $A$ は以下のように変化します． - 初期状態：$A=(2,1,3)$ - $1$ 回目の操作後：$A=(2,3,0)$ - $2$ 回目の操作後：$A=(2,1,1)$