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

Solution:
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeSet;
import java.util.Vector;
import java.util.concurrent.ThreadLocalRandom;

public class CodeForces {

	static class Range {

		String s;

		public Range(String s) {
			this.s = s;
		}

		@Override
		public String toString() {
			return s;
		}
	}

	static class RangeComparator implements Comparator<Range> {

		public int compare(Range o1, Range o2) {
			String[] v1 = o1.s.split("#");
			String[] v2 = o2.s.split("#");
			int val1 = Integer.parseInt(v1[1]) - Integer.parseInt(v1[0]);
			int val2 = Integer.parseInt(v2[1]) - Integer.parseInt(v2[0]);
			if (val1 > val2) {
				return -1;
			} else if (val2 > val1) {
				return 1;
			}
			return o1.s.compareTo(o2.s);
		}

	}

	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static int[] getIntArray(BufferedReader br) throws IOException {
		String line = br.readLine();
		String[] values = line.split(" ");
		int[] arr = new int[values.length];
		for (int i = 0; i < values.length; i++) {
			arr[i] = Integer.parseInt(values[i]);
		}
		return arr;
	}

	public static long[] getLongArray(BufferedReader br) throws IOException {
		String line = br.readLine();
		String[] values = line.split(" ");
		long[] arr = new long[values.length];
		for (int i = 0; i < values.length; i++) {
			arr[i] = Long.parseLong(values[i]);
		}
		return arr;
	}

	public static Set<Integer> getFactors(int n) {
		Set<Integer> set = new HashSet<>();
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				set.add(i);
				set.add(n / i);
			}
		}
		return set;
	}

	public static int[] decode(String s) {
		String[] v = s.split("#");
		int[] arr = new int[2];
		arr[0] = Integer.parseInt(v[0]);
		arr[1] = Integer.parseInt(v[1]);
		return arr;
	}

	public static String encode(int a, int b) {
		return a + "#" + b;
	}

	public static long lcm(long a, long b) {
		BigInteger bigGCD = BigInteger.valueOf(a).gcd(BigInteger.valueOf(b));
		long val = bigGCD.longValue();
		long prod = a * b;
		return prod / val;
	}

	public static Set<Integer> getPrimes() {
		Set<Integer> primes = new HashSet<>();
		for (int i = 2; i < 20000; i++) {
			int fac = 0;
			for (int j = 1; j <= Math.sqrt(i); j++) {
				if (i % j == 0) {
					fac += 2;
				}
			}

			if (fac == 2) {
				primes.add(i);
			}
		}

		System.out.println(primes.size());

		return primes;
	}
	
	public static void dfs(int x,int y,Set<String> set,int n, int m,char p){
		System.out.println(x+" "+y);
		set.add(encode(x, y));
		
		if(p=='d' && (x+1>n || set.contains(encode(x+1, y)))){
			if(!set.contains(encode(x,y-1))){
				p='l';
			}else{
				p='r';
			}
		}else if(p=='l' && (y-1<=0 || set.contains(encode(x, y-1)))){
			if(!set.contains(encode(x-1,y))){
				p='u';
			}else{
				p='d';
			}
		}else if(p=='u' && (x-1<=0 || set.contains(encode(x-1, y)))){
			if(!set.contains(encode(x,y+1))){
				p='r';
			}else{
				p='l';
			}
		}else if(p=='r' && (y+1>m || set.contains(encode(x, y+1)))){
			if(!set.contains(encode(x+1,y))){
				p='d';
			}else{
				p='u';
			}
			p='d';
		}
		
//		System.out.println(p);
		
		if(x+1<=n && !set.contains(encode(x+1,y)) && p=='d'){
			dfs(x+1,y,set,n,m,p);
		}else if(y-1>=1 && !set.contains(encode(x,y-1)) && p=='l' ){
			dfs(x,y-1,set,n,m,p);
		}else if(x-1>=1 && !set.contains(encode(x-1,y)) &&  p=='u'){
			dfs(x-1,y,set,n,m,p);
		}else if(y+1<=m && !set.contains(encode(x,y+1)) && p=='r'){
			dfs(x,y+1,set,n,m,p);
		}
	}
	
	public static String solve(String s){
		int max =0;
		int count=0;
		for(int i=0;i<s.length();i++){
			if(s.charAt(i)=='1'){
				count++;
			}else{
				count=0;
			}
			if(count>max){
				max =count;
			}
		}
		
		String temp ="";
		for(int i=0;i<max;i++){
			temp+="1";
		}
		
		s= s.replaceFirst(temp, "");
		return s;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		int t = Integer.parseInt(line);

		while (t-- > 0) {
			long[] v = getLongArray(br);
			long[] arr = getLongArray(br);
			long k = v[1];
			
			if(k%2!=0){
				long max = Long.MIN_VALUE;
				for(int i=0;i<arr.length;i++){
					max = Math.max(arr[i], max);
				}
				
				for(int i=0;i<arr.length;i++){
					arr[i] = max - arr[i];
				}
				
				for(int i=0;i<arr.length;i++){
					System.out.print(arr[i]+" ");
				}
				System.out.println();
			}else{
				long max = Long.MIN_VALUE;
				for(int i=0;i<arr.length;i++){
					max = Math.max(arr[i], max);
				}
				
				for(int i=0;i<arr.length;i++){
					arr[i] = max - arr[i];
				}
				max = Long.MIN_VALUE;
				for(int i=0;i<arr.length;i++){
					max = Math.max(arr[i], max);
				}
				
				for(int i=0;i<arr.length;i++){
					arr[i] = max - arr[i];
				}
				
				for(int i=0;i<arr.length;i++){
					System.out.print(arr[i]+" ");
				}
				System.out.println();
				
				
			}
			
			

		}
		
		

	}

}