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 seperated integers N (3 <= N <= 20000) and K (1 <= K <= 1000000000). The next line contains N space seperated 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 seperated 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
well i am lagging: 2012-02-03 23:55:36

can someone please tell me reason of WA with my code? Id is 6443856

Prakhar Jain: 2011-12-28 14:16:06

Huh...did it finally......!!!!

Last edit: 2012-01-10 13:11:45
Ajey Golsangi: 2011-10-08 11:13:36

Not for the weak hearted !!!

Anil Purohit: 2011-10-07 05:03:32

what is the previous element for a[0] n next element for a[n-1] ?

Kashyap Krishnakumar: 2011-06-19 07:27:42

N seems to be > 20000.

Omar ElAzazy: 2011-01-22 06:38:45

@Varun, How is your solution dependent on K ?

VinyleEm: 2011-01-22 04:29:14

@anshuman : Its possible to get AC with your algorithm. I just did it.

Varun Jalan: 2010-09-28 07:11:25

@anshuman mishra : how is your solution independent of K ?

anshuman mishra: 2010-09-28 07:11:25

i'm using n*log(max(A[i])) order algo and i'm still getting TLE...is their any better or faster way to solve

[Rampage] Blue.Mary: 2010-09-28 07:11:25

Please read the problem CAREFULLY

Last edit: 2010-01-26 09:13:53

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/