Problem: 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 a of n integers. You are also given an integer k. Lord Omkar wants you to do k operations with this array.

Define one operation as the following: 

  1. Set d to be the maximum value of your array. 
  2. For every i from 1 to n, replace a_{i} with d-a_{i}. 



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

Input

Each test contains multiple test cases. The first line contains the number of cases t (1 ≤ t ≤ 100). Description of the test cases follows.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 10^{18}) – the length of your array and the number of operations to perform.

The second line of each test case contains n integers a_{1},a_{2},...,a_{n} (-10^9 ≤ a_{i} ≤ 10^9) – the initial contents of your array.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each case, print the final version of array a after k operations described above.

Example

Input


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


Output


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]. d = 192.

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

Solution (in PYTHON3):

Solution:
# Design_by_JOKER

from math import *
from cmath import *
from itertools import *
from decimal import *  # su dung voi so thuc
from fractions import *  # su dung voi phan so
from sys import *

# getcontext().prec = x # lay x-1 chu so sau giay phay ( thuoc decimal)
# Decimal('12.3') la 12.3 nhung Decimal(12.3) la 12.30000000012
# Fraction(a) # tra ra phan so bang a (Fraction('1.23') la 123/100 Fraction(1.23) la so khac (thuoc Fraction)
# a = complex(c, d) a = c + d(i) (c = a.real, d = a.imag)
# a.capitalize() bien ki tu dau cua a(string) thanh chu hoa, a.lower() bien a thanh chu thuong, tuong tu voi a.upper()
# a.swapcase() doi nguoc hoa thuong, a.title() bien chu hoa sau dau cach, a.replace('a', 'b', slg)
# a.join['a', 'b', 'c'] = 'a'a'b'a'c, a.strip('a') bo dau va cuoi ki tu 'a'(rstrip, lstrip)
# a.split('a', slg = -1) cat theo ki tu 'a' slg lan(rsplit(), lsplit()), a.count('aa', dau = 0, cuoi= len(a)) dem slg
# a.startswith('a', dau = 0, cuoi = len(a)) co bat dau bang 'a' ko(tuong tu endswith())
# a.index("aa") vi tri dau tien xuat hien (rfind())
# input = open(".inp", mode='r')  a = input.readline()
# out = open(".out", mode='w')# a.index(val)

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    if k > 1:
        k = 2 + int(k % 2)
    while k:
        k -= 1
        x = max(a)
        for y in range(0, n):
            a[y] = x - a[y]
    for x in a:
        print(x, end=' ')
    print()