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.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class B {

	public static void main (String[] args) throws java.lang.Exception {
        InputReader in = new InputReader(System.in);
        int T=in.readInt();
        while(T-->0) {
        	int n=in.readInt();
        	String ks=in.readString();
        	long k=Long.parseLong(ks);
        	long[]nums = new long[n];
        	long max=Long.MIN_VALUE;
        	for(int i=0;i<n;i++) {
        		String ksx=in.readString();
            	nums[i]=Long.parseLong(ksx);
            	max=Math.max(max, nums[i]);
        	}
        	if(k%2==0) {
        		k=2;
        	} else {
        		k=1;
        	}
        	while(k-->0) {
        		long max_2=Long.MIN_VALUE;
	        	for(int i=0;i<n;i++) {
	        		nums[i]=max-nums[i];
	        		max_2=Math.max(nums[i], max_2);
	        	}
	        	max=max_2;
        	}
        	for(long t:nums) System.out.print(t+" ");
        	System.out.println();
        	
        	
        }
    	
		
    		
    	
	}


	static class InputReader {
	    private InputStream stream;
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	    private SpaceCharFilter filter;
	    public InputReader(InputStream stream) {
	        this.stream = stream;
	    }
	    public int read() {
	        if (numChars == -1)
	            throw new InputMismatchException();
	        if (curChar >= numChars) {
	            curChar = 0;
	            try {
	                numChars = stream.read(buf);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	                return -1;
	        }
	        return buf[curChar++];
	    }
	    public int readInt() {
	        int c = read();
	        while (isSpaceChar(c))
	            c = read();
	        int sgn = 1;
	        if (c == '-') {
	            sgn = -1;
	            c = read();
	        }
	        int res = 0;
	        do {
	            if (c < '0' || c > '9')
	                throw new InputMismatchException();
	            res *= 10;
	            res += c - '0';
	            c = read();
	        } while (!isSpaceChar(c));
	        return res * sgn;
	    }
	    public String readString() {
	        int c = read();
	        while (isSpaceChar(c))
	            c = read();
	        StringBuilder res = new StringBuilder();
	        do {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }
	    public boolean isSpaceChar(int c) {
	        if (filter != null)
	            return filter.isSpaceChar(c);
	        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	    }
	    public String next() {
	        return readString();
	    }
	    public interface SpaceCharFilter {
	        public boolean isSpaceChar(int ch);
	    }
	}
	 
	static class IOUtils {
	    public static int[] readIntArray(InputReader in, int size) {
	        int[] array = new int[size];
	        for (int i = 0; i < size; i++)
	            array[i] = in.readInt();
	        return array;
	    }
	}
}