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 A5 {
    
    void solve() {
        int n = cint();
        long[] b = carr_long(n);
        long sum = 0;
        long u = 0;
        for (int i = 0; i < n; i++) {
            sum += b[i];
            u += (i+1);
        }
        
        if (sum % u != 0) {
            cout("NO");
            return;
        }
        long S = sum / u;

        long[] w = new long[n];
        for (int i = 0; i < n; i++) {
            int j = i - 1;
            if (j < 0) j += n;
            w[i] = b[j] - b[i] + S;
            if (w[i] % n != 0 || w[i] < n) {
                cout("NO");
                return;
            }
            w[i] /= n;
        }
        cout("YES");
        cout(w);
        
//        
//
//        double[][] x = new double[n][n+1];
//        ArrayDeque<Integer> koef = new ArrayDeque<>();
//        for (int i = 1; i <= n; i++) {
//            koef.addFirst(i);
//        }
//        for (int i = 0; i < n; i++) {
//            koef.addFirst(koef.removeLast());
//            int j = 0;
//            for (int k : koef) {
//                x[i][j++] = k;
//            }
//            x[i][n] = b[i];
////            cout(Arrays.toString(x[i]));
//        }
//        
//        double[] res = gauss(n, x);
//        
//        long[] w = new long[n];
//        for (int i = 0; i < n; i++) {
//            w[i] = Math.round(res[i]);
//            if (Math.abs(res[i] - w[i]) > 1e-6 || w[i] <= 0) {
//                cout("NO");
//                return;
//            }
//        }
//        
//        cout("YES");
//        cout(w);
    }

    public static double[] gauss(int n, double[][] Matrix) { // copy paste from wikipedia
        double[][] Matrix_Clone = new double[n][n + 1]; //Матрица-дублер
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n + 1; j++)
                Matrix_Clone[i][j] = Matrix[i][j];

        //Прямой ход (Зануление нижнего левого угла)
        for (int k = 0; k < n; k++) //k-номер строки
        {
            for (int i = 0; i < n + 1; i++) //i-номер столбца
                Matrix_Clone[k][i] = Matrix_Clone[k][i] / Matrix[k][k]; //Деление k-строки на первый член !=0 для преобразования его в единицу
            for (int i = k + 1; i < n; i++) //i-номер следующей строки после k
            {
                double K = Matrix_Clone[i][k] / Matrix_Clone[k][k]; //Коэффициент
                for (int j = 0; j < n + 1; j++) //j-номер столбца следующей строки после k
                    Matrix_Clone[i][j] = Matrix_Clone[i][j] - Matrix_Clone[k][j] * K; //Зануление элементов матрицы ниже первого члена][преобразованного в единицу
            }
            for (int i = 0; i < n; i++) //Обновление][внесение изменений в начальную матрицу
                for (int j = 0; j < n + 1; j++)
                    Matrix[i][j] = Matrix_Clone[i][j];
        }

        //Обратный ход (Зануление верхнего правого угла)
        for (int k = n - 1; k > -1; k--) //k-номер строки
        {
            for (int i = n; i > -1; i--) //i-номер столбца
                Matrix_Clone[k][i] = Matrix_Clone[k][i] / Matrix[k][k];
            for (int i = k - 1; i > -1; i--) //i-номер следующей строки после k
            {
                double K = Matrix_Clone[i][k] / Matrix_Clone[k][k];
                for (int j = n; j > -1; j--) //j-номер столбца следующей строки после k
                    Matrix_Clone[i][j] = Matrix_Clone[i][j] - Matrix_Clone[k][j] * K;
            }
        }

        //Отделяем от общей матрицы ответы
        double[] Answer = new double[n];
        for (int i = 0; i < n; i++)
            Answer[i] = Matrix_Clone[i][n];

        return Answer;
    }    
    

    public static void main(String... args) {
        int t = in.nextInt();
        for (int test = 0; test < t; test++) {
            new A5().solve();
        }
        out.flush();
    }


    static final QuickReader in = new QuickReader(System.in);
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 131_072));

    static int cint() {
        return in.nextInt();
    }

    static long clong() {
        return in.nextLong();
    }

    static String cstr() {
        return in.nextLine();
    }

    static int[] carr_int(int n) {
        return in.nextInts(n);
    }

    static long[] carr_long(int n) {
        return in.nextLongs(n);
    }

    static void cout(int... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(long... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(Object o) {
        out.println(o);
    }

    static class QuickReader {
        BufferedReader in;
        StringTokenizer token;

        public QuickReader(InputStream ins) {
            in = new BufferedReader(new InputStreamReader(ins));
            token = new StringTokenizer("");
        }

        public boolean hasNext() {
            while (!token.hasMoreTokens()) {
                try {
                    String s = in.readLine();
                    if (s == null) {
                        return false;
                    }
                    token = new StringTokenizer(s);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return true;
        }

        public String next() {
            hasNext();
            return token.nextToken();
        }

        public String nextLine() {
            try {
                String s = in.readLine();
                token = new StringTokenizer("");
                return s;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] nextInts(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongs(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }
    }
}
