#P1392B. Omkar and Infinity Clock

Omkar and Infinity Clock

Description

Being stuck at home, Ray became extremely bored. To pass time, he asks Lord Omkar to use his time bending power: Infinity Clock! However, Lord Omkar will only listen to mortals who can solve the following problem:

You are given an array aa of nn integers. You are also given an integer kk. Lord Omkar wants you to do kk operations with this array.

Define one operation as the following:

  1. Set dd to be the maximum value of your array.
  2. For every ii from 11 to nn, replace aia_{i} with daid-a_{i}.

The goal is to predict the contents in the array after kk operations. Please help Ray determine what the final sequence will look like!

Each test contains multiple test cases. The first line contains the number of cases tt (1t1001 \le t \le 100). Description of the test cases follows.

The first line of each test case contains two integers nn and kk (1n2105,1k10181 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18}) – the length of your array and the number of operations to perform.

The second line of each test case contains nn integers a1,a2,...,ana_{1},a_{2},...,a_{n} (109ai109)(-10^9 \leq a_{i} \leq 10^9) – the initial contents of your array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

For each case, print the final version of array aa after kk operations described above.

Input

Each test contains multiple test cases. The first line contains the number of cases tt (1t1001 \le t \le 100). Description of the test cases follows.

The first line of each test case contains two integers nn and kk (1n2105,1k10181 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18}) – the length of your array and the number of operations to perform.

The second line of each test case contains nn integers a1,a2,...,ana_{1},a_{2},...,a_{n} (109ai109)(-10^9 \leq a_{i} \leq 10^9) – the initial contents of your array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

Output

For each case, print the final version of array aa after kk operations described above.

Samples

样例输入 1

3
2 1
-199 192
5 19
5 -1 4 2 0
1 2
69

样例输出 1

391 0
0 6 1 3 5
0

Note

In the first test case the array changes as follows:

  • Initially, the array is [199,192][-199, 192]. d=192d = 192.

  • After the operation, the array becomes [d(199),d192]=[391,0][d-(-199), d-192] = [391, 0].