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 ?


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 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.


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

hide comments
samarth5611: 2021-06-07 15:01:55

Try to solve it with a sparse table also :D
I got error with segment tree

robosapien: 2020-07-21 23:45:16

good question for beginners. It's not tough if you think for a while :)

worrywart_ind: 2020-06-13 19:54:16

comments are really depressing for beginners

fahimcp495: 2020-06-02 22:54:58

The value of N is not greater than 20000. when you solve it using segment tree, you should set the size of tree 4*N not 3*N. because the size of segment tree = 2^ceil(log2(20000))+1 = 65536 = 3.2768 * N ~= 4*N

ham163: 2020-05-23 17:41:06

solved with O(n*32) complexity

Last edit: 2020-05-23 17:46:56
prashant05: 2020-04-09 11:23:49

very easy AC in one go!!

kbhartiya83: 2020-04-03 08:00:22


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)


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 :)

Added by:Varun Jalan
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Own Problem, used for Codechef Snackdown