Prefix XORs

时间限制：4s
空间限制：1024MB

题目描述

给定长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$ 与整数 $M$。

一次操作会同时把每个 $A_i$ 替换为前缀异或和

其中 $\oplus$ 表示按位异或。

对于每个 $k=1,2,\ldots,M$，求恰好进行 $k$ 次操作后 $A_N$ 的值。

输入格式

第一行输入两个整数 $N,M$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

依次输出 $M$ 个整数，表示每个 $k$ 对应的答案，相邻整数之间用空格分隔。

样例输入 1

3 2
2 1 3

样例输出 1

0 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

数据范围

对于所有数据，$1\le N,M\le10^6$，$0\le A_i<2^{30}$。