题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$，以及一个整数 $M$。

对于每个 $k=1,2,\cdots,M$，请你求出对 $A$ 恰好进行 $k$ 次如下操作后 $A_N$ 的值。

• 对于所有 $i$（$1\leq i\leq N$），将 $A_i$ 的值替换为 $A_1\oplus A_2\oplus \cdots\oplus A_i$。这个替换对所有 $i$ 同时进行。

这里，$\oplus$ 表示按位异或（bitwise XOR）运算。

按位异或（bitwise XOR）运算的定义如下：对于非负整数 $A,B$，$A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）上的数，如果 $A,B$ 在该位上只有一个为 $1$，则结果为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制表示为：$011\oplus 101=110$）。 一般来说，$k$ 个整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或为 $(\dots((p\_1\oplus p\_2)\oplus p\_3)\oplus\dots\oplus p\_k)$，并且可以证明其结果与顺序无关。

输入格式

输入从标准输入读取，格式如下：

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

输出格式

请输出每个 $k$ 的答案，空格分隔。

样例 1

输入

3 2
2 1 3

输出

0 1

样例 2

输入

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}$
• 输入的所有值均为整数

样例解释 1

每次操作后，$A$ 的变化如下：

• 初始状态：$A=(2,1,3)$
• 第 1 次操作后：$A=(2,3,0)$
• 第 2 次操作后：$A=(2,1,1)$

由 ChatGPT 4.1 翻译