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.util.*;
import java.lang.*;
import java.io.*;

public class B {
	private static FastReader fr;
	private static OutputStream out;
	private static int mod = (int)(1e9+7);
	
	private void solve() {
		int t = fr.nextInt();
		while(t-- > 0) {
			int n = fr.nextInt();
			long k = fr.nextLong();
			int arr[] = new int[n];
			int max = Integer.MIN_VALUE;
			for(int i=0;i<n;i++) {
				arr[i] = fr.nextInt();
				max = Math.max(max, arr[i]);
			}
			
			if(k > 0) {
				k--;
				int temp = Integer.MIN_VALUE;
				for(int i=0;i<n;i++) {
					arr[i] = max - arr[i];
					temp = Math.max(temp, arr[i]);
				}
				max = temp;
			}
			
			if(k % 2 == 1) {
				for(int i=0;i<n;i++) {
					arr[i] = max - arr[i];
				}
			}
			
			for(int val : arr)
				print(val + " ");
			println();
		}
	}
	
	private static int modInverse(int a) { 
        int m0 = mod; 
        int y = 0, x = 1; 
  
        if (mod == 1) 
            return 0; 
  
        while (a > 1) { 
            int q = (int)(a / mod); 
  
            int t = mod;  
            mod = a % mod; 
            a = t; 
            t = y; 
   
            y = x - q * y; 
            x = t; 
        } 
   
        if (x < 0) 
            x += m0; 
  
        return x; 
    }
	
	public static void main(String args[]) throws IOException{
		new B().run();
	}
	
	private ArrayList<Integer> factors(int n, boolean include){
		ArrayList<Integer> factors = new ArrayList<>();
		if(n < 0)
			return factors;
		
		if(include) {
			factors.add(1);
			if(n > 1)
				factors.add(n);
		}
		
		int i = 2;
		for(;i*i<n;i++) {
			if(n % i == 0) {
				factors.add(i);
				factors.add(n / i);
			}
		}
		
		if(i * i == n) {
			factors.add(i);
		}
		
		return factors;
	}
	
	private ArrayList<Integer> PrimeFactors(int n) {
	    ArrayList<Integer> primes = new ArrayList<>();
	 
	    int i = 2;
	    while (i * i <= n) {
	      if (n % i == 0) {
	        primes.add(i);
	        n /= i;
	        
	        while (n % i == 0) {
	        	primes.add(i);
	        	n /= i;
	        }
	      }
	 
	      i++;
	    }
	    
	    if(n > 1)
	    	primes.add(i);
	    
	    return primes;
	  }
	
	private boolean isPrime(int n) {
		if(n == 0 || n == 1) {
			return false;
		}
		
		if(n % 2 == 0) {
			return false;
		}
		
		for(int i=3;i*i<=n;i+=2) {
			if(n % i == 0) {
				return false;
			}
		}
		
		return true;
	}

	private ArrayList<Integer> Sieve(int n){
		boolean bool[] = new boolean[n+1];
		Arrays.fill(bool, true);
		bool[0] = bool[1] = false;
		
		for(int i=2;i*i<=n;i++) {
			if(bool[i]) {
				int j = 2;
				while(i*j <= n) {
					bool[i*j] = false;
					j++;
				}
			}
		}
		
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i=2;i<=n;i++) {
			if(bool[i])
				primes.add(i);
		}
		
		return primes;
	}
	
	private HashMap<Integer, Integer> addToHashMap(HashMap<Integer, Integer> map, int arr[]){
		for(int val: arr) {
			if(!map.containsKey(val)) {
				map.put(val, 1);
			}else {
				map.put(val, map.get(val) + 1);
			}
		}
		return map;
	}
	
	private int factorial(int n) {
		long fac = 1;
		for(int i=2;i<=n;i++) {
			fac *= i;
			fac %= mod;
		}
		return (int)(fac % mod);
	}

//	private static int pow(int base,int exp){
//		if(exp == 0){
//			return 1;
//		}else if(exp == 1){
//			return base;
//		}
//		int a = pow(base,exp/2);
//		a = ((a % mod) * (a % mod)) % mod;
//		if(exp % 2 == 1) {
//			a = ((a % mod) * (base % mod));
//		}
//		return a;
//	}

	private static int gcd(int a,int b){
		if(a == 0){
			return b;
		}
		
		return gcd(b%a,a);
	}
	
	private static int lcm(int a,int b){
		return (a * b)/gcd(a,b);
	}
	
	private void run() throws IOException{
		fr = new FastReader();
		out = new BufferedOutputStream(System.out);
		solve();
		out.flush();
		out.close();
	}
	
	private static class FastReader{
		private static BufferedReader br; 
		private static StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedOutputStream(System.out);
		}
		
		public String next() {
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken();
		}
		
		public String nextLine() { 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		 
		public char[] nextCharArray() {
			return next().toCharArray();
		}
		
		public int[] nextIntArray(int n) {
			int arr[] = new int[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
		
		public long[] nextLongArray(int n) {
			long arr[] = new long[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public String[] nextStringArray(int n) {
			String arr[] = new String[n];
			for(int i=0;i<n;i++) {
				arr[i] = next();
			}
			return arr;
		}
		
	}

	public static void print(Object str) {
        try {
            out.write(str.toString().getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println(Object str) {
        try {
            out.write((str.toString() + "\n").getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println() {
		println("");
	}
	
	public static void printArray(Object str[]){
		for(Object s : str) {
			try {
	            out.write(str.toString().getBytes());
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
		}
	}
}