我们定义：

• 给定一个长度为 $n$ 的数列 $A$；
• 对于任意 $1\le i\le n$，令 $B_i$ 为 $A$ 前 $i$ 项的异或和；
• 记 $f(A)=B$。

给定 $A_0$，若 $A_i=f(A_{i-1})\ (i\ge1)$，请你求出数列 $A_t$。

输入格式

第一行一个整数 $n,t$。

第二行 $n$ 个整数，表示数列 $A_0$。

输出格式

仅一行 $n$ 个整数，表示数列 $A_t$。

样例

输入样例 1

3 3
1 2 3

输出样例 1

1 3 1

数据规模与约定

• 测试点 $1$：$n,t\le 10$；
• 测试点 $2\sim 3$：$n,t\le 10^3$；
• 测试点 $4\sim 6$：$n,t\le 2\times 10^5$。
• 测试点 $7\sim 10$：无特殊限制。

对于所有数据，$1\le n\le 2\times 10^5$，$1\le t\le 10^9$，$0\le A_{0,i}\le 10^9$，保证参数 $t$ 在给定范围内随机生成。