XORROUND - XOR Rounds

You are given a cyclic array A having N numbers. In an XOR round, each element of the array A is replaced by the bitwise XOR (Exclusive OR) of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after K such XOR rounds?

Input

The first line contains the number of test cases T (T <= 50). There follow 2T lines, 2 per test case. The first line contains two space separated integers N (3 <= N <= 500) and K (1 <= K <= 1000000000). The next line contains N space separated integers Ai (0 <= Ai <= 1000000000), which are the initial values of the elements in array A.

Output

Output T lines, one per test case. For each test case, output a space separated list of N integers, specifying the contents of array A after K XOR rounds.

Example

Input:
2
3 1
1 2 3
5 100
1 11 111 1111 11111

Output:
0 0 0
11117 101 1075 12127 12081

Added by:Varun Jalan
Date:2010-01-11
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Own Problem, used for Codechef Snackdown http://www.codechef.com/

hide comments
2019-03-19 21:15:17
tricky based question!!
write binary of k .. and do something with the set bits of k :)
In case of k=2^x x is any +ve no.
for k=4; a[i]=a[i]^a[i-4]^a[i+4]; similary true for all k which is power of 2;
and do this for set bits of k;
2016-01-21 06:13:03 Dr Mandioca
Nice problem!
2014-01-14 19:04:21 anurag garg
My 200th on spoj.....bits logic

Last edit: 2014-01-15 17:22:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.