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.*;
import java.util.*;
public class Main {

    public static void main(String args[]) {
        FastIO io = new FastIO();
        int T = io.nextInt();
        for (int t = 1; t <= T; t++) {
            int N = io.nextInt();
            long K = io.nextLong();
            int[] arr = new int[N];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                arr[i] = io.nextInt();
                max = Math.max(arr[i], max);
            }

            int max2 = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                arr[i] = max - arr[i];
                max2 = Math.max(max2, arr[i]);
            }

            if (K % 2 == 1) {
                for (int i = 0; i < N; i++) {
                    io.printls(arr[i]);
                }
                io.write((byte) 10);
            } else {
                for (int i = 0; i < N; i++) {
                    arr[i] = max2 - arr[i];
                }

                for (int i = 0; i < N; i++) {
                    io.printls(arr[i]);
                }
                io.write((byte) 10);
            }

        }


        io.flushbuffer();
    }

    private static class FastIO {
        private static final int DEFAULT_BUFFER_SIZE = 65536;
        private static final int DEFAULT_LONG_SIZE = 20;
        private static final int DEFAULT_INT_SIZE = 11;
        private static final int DEFAULT_LINE_SIZE = 30;
        private static final int EOF = -1;

        private static final byte ASCII_n = 10;
        private static final byte ASCII_r = 13;
        private static final byte ASCII_space = 32;
        private static final byte ASCII_minus = 45;
        private static final byte ASCII_0 = 48;
        private static final byte ASCII_9 = 57;

        private final DataInputStream din;
        private final DataOutputStream dout;

        private byte[] inbuffer;
        private int inbufferpointer, bytesread;
        private byte[] outbuffer;
        private int outbufferpointer;

        private byte[] bytebuffer;
        private char[] charbuffer;

        private FastIO(int inbuffersize, int outbuffersize) {
            this.din = new DataInputStream(System.in);
            this.dout = new DataOutputStream(System.out);

            this.inbuffer = new byte[inbuffersize];
            this.inbufferpointer = 0;
            this.bytesread = 0;
            this.outbuffer = new byte[outbuffersize];
            this.outbufferpointer = 0;

            this.bytebuffer = new byte[DEFAULT_LONG_SIZE];
            this.charbuffer = new char[DEFAULT_LINE_SIZE];
        }

        private FastIO() {
            this(DEFAULT_BUFFER_SIZE, DEFAULT_BUFFER_SIZE);
        }

        private FastIO(int buffersize) {
            this(buffersize, buffersize);
        }

        private byte read() {
            if (inbufferpointer == bytesread)
                fillbuffer();
            return bytesread == EOF ? EOF : inbuffer[inbufferpointer++];
        }

        private void fillbuffer() {
            try {
                bytesread = din.read(inbuffer, inbufferpointer = 0, inbuffer.length);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        private void write(byte b) {
            if (outbufferpointer == outbuffer.length)
                flushbuffer();
            outbuffer[outbufferpointer++] = b;
        }

        private void flushbuffer() {
            if (outbufferpointer != 0) {
                try {
                    dout.write(outbuffer, 0, outbufferpointer);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                outbufferpointer = 0;
            }
        }

        private char nextChar() {
            byte b;
            while (isSpace(b = read()))
                ;
            return (char) b;
        }

        private String next() {
            byte b;
            while (isSpace(b = read())) {
            }
            int index = 0;
            do {
                charbuffer[index++] = (char) b;
            } while (!isSpace(b = read()));
            return new String(charbuffer, 0, index);
        }

        private String nextLine() {
            byte b;
            int index = 0;
            while (!isLine(b = read()))
                charbuffer[index++] = (char) b;
            return new String(charbuffer, 0, index);
        }

        private int nextInt() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            int result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private long nextLong() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            long result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private float nextFloat() {
            byte b;
            while (isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == ASCII_minus) {
                negative = true;
                b = read();
            }
            float f = 0;
            do {
                f = f * 10 + b - ASCII_0;
            } while (isDigit(b = read()));
            int d = 1;
            b = read();
            do {
                f = f * 10 + b - ASCII_0;
                d = d * 10;
            } while (isDigit(b = read()));
            return f / d;

        }

        private void print(char c) {
            write((byte) c);
        }

        private void print(char[] c) {
            for (int i = 0; i < c.length; i++) {
                write((byte) c[i]);
            }
        }

        private void print(String s) {
            for (int i = 0; i < s.length(); i++) {
                write((byte) s.charAt(i));
            }
        }

        private void println(int i) {
            if (i == 0) {
                write(ASCII_0);
            } else {
                if (i < 0) {
                    write(ASCII_minus);
                    i = -i;
                }
                int index = 0;
                while (i > 0) {
                    bytebuffer[index++] = (byte) ((i % 10) + ASCII_0);
                    i /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
            write(ASCII_n);
        }

        private void printls(int i) {
            if (i == 0) {
                write(ASCII_0);
            } else {
                if (i < 0) {
                    write(ASCII_minus);
                    i = -i;
                }
                int index = 0;
                while (i > 0) {
                    bytebuffer[index++] = (byte) ((i % 10) + ASCII_0);
                    i /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
            write(ASCII_space);
        }

        private void print(long l) {
            if (l == 0) {
                write(ASCII_0);
            } else {
                if (l < 0) {
                    write(ASCII_minus);
                    l = -l;
                }
                int index = 0;
                while (l > 0) {
                    bytebuffer[index++] = (byte) ((l % 10) + ASCII_0);
                    l /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
        }

        private boolean isLine(byte b) {
            return b == ASCII_r || b == ASCII_n || b == EOF;
        }

        private boolean isSpace(byte b) {
            return b <= ASCII_space && b >= 0;
        }

        private boolean isDigit(byte b) {
            return b >= ASCII_0 && b <= ASCII_9;
        }
    }
}