{"raw_statement":[{"iden":"problem statement","content":"You are given an integer sequence of length $N$: $A=(A_1,A_2,\\cdots,A_N)$, and an integer $M$.\nFor each $k=1,2,\\cdots,M$, find the value of $A_N$ after doing the operation below $k$ times.\n\n*   For every $i$ ($1 \\leq i \\leq N$), simultaneously, replace the value of $A_i$ with $A_1 \\oplus A_2 \\oplus \\cdots \\oplus A_i$.\n\nHere, $\\oplus$ denotes bitwise $\\mathrm{XOR}$.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows:\n\n*   When $A \\oplus B$ is written in base two, the digit in the $2^k$'s place ($k \\geq 0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor example, we have $3 \\oplus 5 = 6$ (in base two: $011 \\oplus 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ integers $p_1, p_2, p_3, \\dots, p_k$ is defined as $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$. We can prove that this value does not depend on the order of $p_1, p_2, p_3, \\dots p_k$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^6$\n*   $1 \\leq M \\leq 10^6$\n*   $0 \\leq A_i < 2^{30}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3 2\n2 1 3"},{"iden":"sample output 1","content":"0 1\n\nEach operation changes $A$ as follows.\n\n*   Initially: $A=(2,1,3)$.\n*   After the first operation: $A=(2,3,0)$.\n*   After the second operation: $A=(2,1,1)$."},{"iden":"sample input 2","content":"10 12\n721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427"},{"iden":"sample output 2","content":"716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}