[ARC137D] Prefix XORs
配点 : 点
問題文
長さ の整数列 ，及び整数 が与えられます．
各 について，以下の操作をちょうど 回行ったあとの の値を求めてください．
- すべての () について， の値を で置き換える． この置き換えはすべての に対して同時に行う．
ただしここで， はビット単位 演算を表します．
ビット単位 $\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 の順番によらないことが証明できます。
制約
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
出力
各 に対する答えを空白区切りで出力せよ．
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