AND Rounds

Problem code: RESN01

All submissions for this problem are available.

Problem statement updated.

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

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

Date: 2009-12-16
Time limit: 5

s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

According to my understanding

pragrame @ 20 Dec 2009 04:17 PM

According to my understanding of the problem, shouldn't the 2nd output be

"1 1 1 1 1"?

Its BITWISE AND, not LOGICAL

syco @ 20 Dec 2009 04:20 PM

Its BITWISE AND, not LOGICAL AND. In C,C++, etc you can use & operator to perform BITWISE AND.

yeah, but isn't after 100

resnk_DareToCode @ 20 Dec 2009 04:38 PM

yeah, but isn't after 100 rounds bitwise AND of each will result one ?

@admin can u explain the

Blitzkrieg @ 20 Dec 2009 04:43 PM

@admin

can u explain the output of 2nd test  case . According to my understanding  I m getting "1  1  1  1   1 "

The answer should be "1 1 1 1

syco @ 20 Dec 2009 04:44 PM

The answer should be "1 1 1 1 1" for the second test case. Updated

Yeah, looks like the sample

triplem @ 20 Dec 2009 04:44 PM

Yeah, looks like the sample output is wrong.

The answer should be "1 1 1 1

syco @ 20 Dec 2009 04:45 PM

The answer should be "1 1 1 1 1" for the second test case. Updated

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions