题目描述

给定一个长度为 $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_1 \\oplus A_2 \\oplus \\cdots \\oplus A_i$ 替换 $A_i$ 的值。

这里，$\\oplus$ 表示按位异或。

什么是按位异或？

非负整数 $A$ 和 $B$ 的按位异或 $A \\oplus 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)$。我们可以证明这个值不依赖于 $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)$。
• 第一次操作后：$A=(2,3,0)$。
• 第二次操作后：$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