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.*;

public class CodeForces{
    /*-------------------------------------------EDITING CODE STARTS HERE-------------------------------------------*/

    public static void main(String[] args) throws IOException{
        openIO();
        int testCase = 1;
        testCase = sc.nextInt();
        for (int i = 1; i <= testCase; i++) solve(i);
        closeIO();
    }
    public static void solve(int tCase)throws IOException {
        int n = sc.nextInt();
        long[] brr = new long[n];
        long sum = 0;
        for(int i=0;i<n;i++){
            brr[i] = sc.nextInt();
            sum += brr[i];
        }
        long t = n * (n+1L) / 2;
        if( sum % t !=0){
            out.println("NO");
            return;
        }
        sum /= t;
        long[] ans = new long[n];
        for(int i=0;i<n;i++){
            long curr = sum - brr[i] + brr[_mod(i-1,n)];
            if(curr % n != 0){
                out.println("NO");
                return;
            }
            ans[i] = curr / n;
            if(ans[i] <=0 ){
                out.println("NO");
                return;
            }

        }
        out.println("YES");
        for(long ele : ans)out.println(ele);



    }
    private static int _mod(int x, int n){return (x+n) % n;}
   



    /*-------------------------------------------EDITING CODE ENDS HERE-------------------------------------------*/
    static FastestReader sc;
    static PrintWriter out;
    private static void openIO() throws IOException{
        sc = new FastestReader();
        out = new PrintWriter(System.out);
    }

    /*------------------------------------------HELPER FUNCTION STARTS HERE------------------------------------------*/

    public static int mod = (int) 1e9 + 7;
    private static int mod2 =  998244353;
    public static int inf_int = (int) 2e9 + 10;
    public static  long inf_long = (long) 2e15;


    public static int _digitCount(long num,int base){
        return (int)(1 + Math.log(num)/Math.log(base));
    }
    public static long _fact(int n){
        long ans = 1;
        for(int i=2;i<=n;i++)
            ans = ans * i % mod;
        return ans;
    }
    // time : O(r)
    public static int _ncr(int n,int r){
        if (r > n) return 0;
        long[]  inv = new long[r + 1];
        inv[0] = 1;
        if(r+1>=2)
            inv[1] = 1;

        // Getting the modular inversion
        // for all the numbers
        // from 2 to r with respect to mod
        for (int i = 2; i <= r; i++)
            inv[i] = mod - (mod / i) * inv[(mod % i)] % mod;

        int ans = 1;

        // for 1/(r!) part
        for (int i = 2; i <= r; i++)
            ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);

        // for (n)*(n-1)*(n-2)*...*(n-r+1) part
        for (int i = n; i >= (n - r + 1); i--)
            ans =  (((ans % mod) * (i % mod)) % mod);
        return ans;
    }

    // euclidean algorithm time O(max (loga ,logb))
    public static long _gcd(long a, long b) {
        if (a == 0)
            return b;
        return _gcd(b % a, a);
    }

    public static long _lcm(long a, long b) {
        // lcm(a,b) * gcd(a,b) = a * b
        return (a / _gcd(a, b)) * b;
    }


    // binary exponentiation time O(logn)
    public static long _power(long x, long n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans *= x;
                ans %= mod;
                n--;
            } else {
                x *= x;
                x %= mod;
                n >>= 1;
            }
        }
        return ans;
    }
    //sieve/first divisor time : O(mx * log ( log (mx) ) )
    public static int[]  _seive(int mx){
        int[] firstDivisor = new int[mx+1];
        for(int i=0;i<=mx;i++)firstDivisor[i] = i;
        for(int i=2;i*i<=mx;i++)
            if(firstDivisor[i] == i)
                for(int j = i*i;j<=mx;j+=i)
                    firstDivisor[j] = i;
        return firstDivisor;
    }

    private static boolean _isPrime(long x){
        for(long i=2;i*i<=x;i++)
            if(x%i==0)return false;
        return true;
    }

    public static void _sort(int[] arr,boolean isAscending){
        int n = arr.length;
        List<Integer> list = new ArrayList<>();
        for(int ele : arr)list.add(ele);
        Collections.sort(list);
        if(!isAscending)Collections.reverse(list);
        for(int i=0;i<n;i++)arr[i] = list.get(i);
    }

    public static void _sort(long[] arr,boolean isAscending){
        int n = arr.length;
        List<Long> list = new ArrayList<>();
        for(long ele : arr)list.add(ele);
        Collections.sort(list);
        if(!isAscending)Collections.reverse(list);
        for(int i=0;i<n;i++)arr[i] = list.get(i);
    }
    /*------------------------------------------HELPER FUNCTION ENDS HERE-------------------------------------------*/

    /*-------------------------------------------FAST INPUT STARTS HERE---------------------------------------------*/

    public static void closeIO() throws IOException{
        out.flush();
        out.close();
        sc.close();
    }
    private static final class FastestReader {
        private static final int BUFFER_SIZE = 1 << 16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastestReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastestReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }

        private int skip() throws IOException {
            int b;
            //noinspection StatementWithEmptyBody
            while ((b = read()) != -1 && isSpaceChar(b)) {}
            return b;
        }

        public String next() throws IOException {
            int b = skip();
            final StringBuilder sb = new StringBuilder();
            while (!isSpaceChar(b)) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) { return -ret; }
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) { return -ret; }
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg) { return -ret; }
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) { buffer[0] = -1; }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) { fillBuffer(); }
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            din.close();
        }
    }
    /*---------------------------------------------FAST INPUT ENDS HERE ---------------------------------------------*/
}