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. Then follow 2t lines, two per test case. The first line contains two space separated integers n (3 ≤ n ≤ 20000) and k (1 ≤ k ≤ 109). The next line contains n space separated integers Ai (0 ≤ Ai ≤ 109), which are the initial values of the elements in array A.

Output

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