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
kbhartiya83: 2020-04-03 08:00:22

NAAN

Last edit: 2020-04-03 08:54:07
x4fectax: 2020-01-09 17:15:44

oh my god ez problem ac forst got lmao so ez i am vry good tehc O(nlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlognlogn)

/s

hoangkimduc: 2019-11-01 09:54:42

AC on second go. Yeahezzz

cyber_psych0: 2019-08-24 09:54:43

Hurray!! AC in one go :)

nik6: 2019-08-01 10:21:07

Last edit: 2019-08-01 10:30:44
sky_scraper: 2019-06-12 22:21:34

Implemented seg tree in one go with the actual logic. Segtree part is easy, try to prove to logic.

akshat_pat: 2018-04-10 16:29:03

AC in one go :)

shubhshrma: 2018-01-03 11:37:34

Solved with simple arrays in 0.22s :)

spojabhi: 2017-12-20 21:34:54

good implementation of segment tree *_*

hemakshis: 2017-06-24 18:32:25

My first segment tree problem with A.C. in one go..yippie :)


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/