n towns are arranged in a circle sequentially. The towns are numbered from 1 to n in clockwise order. In the i-th town, there lives a singer with a repertoire of a_i minutes for each i ∈ [1, n].

Each singer visited all n towns in clockwise order, starting with the town he lives in, and gave exactly one concert in each town. In addition, in each town, the i-th singer got inspired and came up with a song that lasts a_i minutes. The song was added to his repertoire so that he could perform it in the rest of the cities.

Hence, for the i-th singer, the concert in the i-th town will last a_i minutes, in the (i + 1)-th town the concert will last 2 ⋅ a_i minutes, ..., in the ((i + k) mod n + 1)-th town the duration of the concert will be (k + 2) ⋅ a_i, ..., in the town ((i + n - 2) mod n + 1) — n ⋅ a_i minutes.

You are given an array of b integer numbers, where b_i is the total duration of concerts in the i-th town. Reconstruct any correct sequence of positive integers a or say that it is impossible.

Input

The first line contains one integer t (1 ≤ t ≤ 10^3) — the number of test cases. Then the test cases follow.

Each test case consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 4 ⋅ 10^4) — the number of cities. The second line contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ 10^{9}) — the total duration of concerts in i-th city.

The sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, print the answer as follows:

If there is no suitable sequence a, print NO. Otherwise, on the first line print YES, on the next line print the sequence a_1, a_2, ..., a_n of n integers, where a_i (1 ≤ a_i ≤ 10^{9}) is the initial duration of repertoire of the i-th singer. If there are multiple answers, print any of them.

Example

Input


4
3
12 16 14
1
1
3
1 2 3
6
81 75 75 93 93 87


Output


YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5 

Note

Let's consider the 1-st test case of the example:

  1. the 1-st singer in the 1-st city will give a concert for 3 minutes, in the 2-nd — for 6 minutes, in the 3-rd — for 9 minutes; 
  2. the 2-nd singer in the 1-st city will give a concert for 3 minutes, in the 2-nd — for 1 minute, in the 3-rd - for 2 minutes; 
  3. the 3-rd singer in the 1-st city will give a concert for 6 minutes, in the 2-nd — for 9 minutes, in the 3-rd — for 3 minutes. 
import java.io.*;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class E {

    private final boolean MULTI_TEST = true;
    private final String FILE_NAME = "";

    private void solve() {
        int n = ri();
        long[] b = new long[n];
        for(int i = 0; i < n; i++) {
            b[i] = rl();
        }
        long sumB = sum(b);
        long sumA = 2 * sumB / ((long) n * (n + 1));
        long[] a = new long[n];
        boolean flag = true;
        for (int i = 1; i < n; i++) {
            a[i] = (b[i-1] - b[i] + sumA)/n;
            if (a[i] <= 0) {
                flag = false;
                break;
            }
        }

        a[0] = (b[n-1] - b[0] + sumA)/n; //if n == 1, then a[0] = sumA/n = sumA - true
        if(a[0] <= 0) flag = false;
        if(!flag || sum(a) != sumA) {
            out.println("NO");
        } else {
            out.println("YES");
            StringBuilder builder =new StringBuilder();
            for(long l : a) {
                builder.append(l).append(" ");
            }
            out.println(builder);
        }
    }

    //////////////////////////////////////////////////////////////////

    long sqrtLong(long x) {
        long root = (long) Math.sqrt(x);
        while (root * root > x) --root;
        while ((root + 1) * (root + 1) <= x) ++root;
        return root;
    }

    int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    int phi(int n) {
        int result = n;
        for (int i = 2; i * i <= n; ++i)
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        if (n > 1)
            result -= result / n;
        return result;
    }

    int factmod(int n, int p) {
        int res = 1;
        while (n > 1) {
            res = (res * ((n / p) % 2 == 1 ? p - 1 : 1)) % p;
            for (int i = 2; i <= n % p; ++i)
                res = (res * i) % p;
            n /= p;
        }
        return res % p;
    }

    int binpow(int a, int n) {
        int res = 1;
        while (n != 0) {
            if ((n & 1) != 0)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    String solPyatnashki() {
        int a[] = new int[16];
        for (int i = 0; i < 16; ++i)
            a[i] = ri();

        int inv = 0;
        for (int i = 0; i < 16; ++i)
            if (a[i] != 0)
                for (int j = 0; j < i; ++j)
                    if (a[j] > a[i])
                        ++inv;
        for (int i = 0; i < 16; ++i)
            if (a[i] == 0)
                inv += 1 + i / 4;


        return ((inv & 1) != 0 ? "No Solution" : "Solution Exists");
    }

    boolean isPrime(int number) {
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return number > 1;
    }

    boolean[] primes(int border) {
        boolean[] isPrimes = new boolean[border + 1];
        Arrays.fill(isPrimes, true);
        isPrimes[0] = false;
        isPrimes[1] = false;
        for (int i = 2; i < border + 1; i++) {
            if (!isPrimes[i]) continue;
            for (int k = i * 2; k < border; k += i) {
                isPrimes[k] = false;
            }
        }
        return isPrimes;
    }

    int[] sort(int[] arr) {
        Integer[] a = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        return arr;
    }

    long[] sort(long[] arr) {
        Long[] a = new Long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            a[i] = arr[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        return arr;
    }

    int max(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    long max(long[] a) {
        long max = Long.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    int min(int[] a) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
        }
        return min;
    }

    long min(long[] a) {
        long min = Long.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
        }
        return min;
    }

    long sum(long[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++) {
            s += a[i];
        }
        return s;
    }

    long fastMod(String s1, long n2) {
        long num = 0;
        for (int i = 0; i < s1.length() - 1; i++) {
            num += Integer.parseInt(String.valueOf(s1.charAt(i)));
            num *= 10;
            if (num >= n2) {
                num = num % n2;
            }
        }
        return (num + Integer.parseInt(String.valueOf(s1.charAt(s1.length() - 1)))) % n2;
    }

    //////////////////////////////////////////////////////////////////

    private boolean yesNo(boolean yes) {
        return yesNo(yes, "YES", "NO");
    }

    private boolean yesNo(boolean yes, String yesString, String noString) {
        out.println(yes ? yesString : noString);
        return yes;
    }

    //////////////////////////////////////////////////////////////////

    private long rl() {
        return Long.parseLong(rs());
    }

    private double rd() {
        return Double.parseDouble(rs());
    }

    private int[] ria(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = ri();
        return a;
    }

    private int ri() {
        return Integer.parseInt(rs());
    }

    private String rs() {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) return null;
            tok = new StringTokenizer(nextLine);
        }

        return tok.nextToken();
    }

    private String readLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    //////////////////////////////////////////////////////////////////

    private BufferedReader in;
    private StringTokenizer tok;
    private PrintWriter out;

    private void initFileIO(String inputFileName, String outputFileName) throws FileNotFoundException {
        in = new BufferedReader(new FileReader(inputFileName));
        out = new PrintWriter(outputFileName);
    }

    private void initConsoleIO() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
    }

    private void initIO() throws IOException {
        Locale.setDefault(Locale.US);

        if (!FILE_NAME.isEmpty()) {
            initFileIO(FILE_NAME + ".in", FILE_NAME + ".out");
        } else {
            if (new File("input.txt").exists()) {
                initFileIO("input.txt", "output.txt");
            } else {
                initConsoleIO();
            }
        }

        tok = new StringTokenizer("");
    }

    //////////////////////////////////////////////////////////////////

    private void run() {
        try {
            long timeStart = System.currentTimeMillis();
            initIO();
            if (MULTI_TEST) {
                int t = ri();
                while (t-- > 0) {
                    solve();
                    out.flush();
                }
            } else
                solve();
            out.close();
            long timeEnd = System.currentTimeMillis();
            System.err.println("Time(ms) = " + (timeEnd - timeStart));
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
    }

    public static void main(String[] args) {
        new E().run();
    }

    ///////////////////////////////////////////////////////////////////
}
