ANDROUND - AND Rounds


You are given a cyclic array A having N numbers. In an AND round, each element of the array A is replaced by the bitwise AND of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after K such AND 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 <= 20000) 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 AND rounds.

Example

Sample Input:
2 
3 1 
1 2 3 
5 100 
1 11 111 1111 11111 
 
Sample Output:
0 0 0 
1 1 1 1 1

hide comments
sfialok98: 2017-05-28 12:01:12

AC finally...!!!
Did with segment tree...

xariniov9: 2017-05-26 10:48:19

Why the answer of first test case 0 0 0?

should not it be 0 0 2 ?

got it.. array is cyclic

Last edit: 2017-05-26 10:51:24
nabila ahmed: 2016-11-02 06:08:49

Very interesting problem. Solved with BIT :)

dwij28: 2016-08-22 17:30:29

I don't know about how others solved it but for me Segment Tree worked wonders, constant TLE and WA before that.

Last edit: 2016-08-22 17:30:42
praval_singhal: 2016-07-13 22:25:21

What a blunder i was committing. 0&A=a. :P finally AC

karthik1997: 2016-06-11 19:42:01

Uff ... Solved with O(n*32) approach ... ( Use Int)...

Please see . All elements are simultaneously " & " ed ... So after kth iteration

a[i] =a[i-k]& a[i-k+1].....&a[i] &a[i+1] .... a[i+k]

Wasted a lot of time on that :( .. Try spoj XORROUND after this ....

Last edit: 2016-06-11 19:43:16
minhthai: 2016-02-29 10:06:45

it can be solved in ~O(n) :)

Last edit: 2016-02-29 10:06:53
codezilla: 2016-02-23 20:13:57

Use int instead of long long to ensure no TLE.

pika_pika: 2015-10-24 09:56:39

The judge is checking whitespaces at the end of each lines. got many WA due to that. Please fix.

Ashish Tilokani: 2015-01-25 11:09:17

n>20000


Added by:Varun Jalan
Date:2010-01-11
Time limit:1s
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/