Prefix XORs

Time Limit: 10s

Memory Limit: 1024 MB

Problem Statement

You are given an integer sequence of length $N$: $A=(A_1,A_2,\dots,A_n)$, and an integer $M$.

For each $k=1,2,\dots,M$, find the value of $A=\{A_1,A_2,\dots,A_n\}$ after doing the operation below $k$ times.

• For every $i(1\leq i\leq N)$, replace the value $A_i$ with $A_1\bigoplus A_2\bigoplus\dots\bigoplus A_i$.
• Note that once the previous number $A_i$ is modified, the subsequent numbers should also be operated with this new $A_i$.

Here, $\bigoplus$ denotes bitwise XOR.

• What is bitwise XOR?
  • The bitwise XOR of non-negative integers $A$ and $B$, $A\bigoplus B$, is defined as follows.
  • When $A\bigoplus B$ is written in base two, the digit in the $2^k$'s place ($k\geq0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise.

Input

The first line contains two integers $N,M(1\leq N\leq10^5,1\leq M\leq10^9)$.

The second line contains $N$ integers $A_1,A_2,\dots,A_N(0\leq A_i<2^{30})$.

Output

Print the answer $N$ integers after $M$ operations, separated by spaces.

3 2
2 1 3

2 1 1

10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

721939838 337089195 171851101 1069204754 1069907851 277835428 942783328 988367899 624897153 844652404

Explanation

For the first sample, each operation changes $A$ as follows.

• Initially : $A=(2,1,3)$.
• After the first operation : $A=(2,3,0)$
• After the second operation: $A=(2,1,1)$