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 cf {
 
    public static void main(String[] args){
 
        FastScanner sc = new FastScanner();
        int x = sc.nextInt();
        //int x=1;
        while(x-- > 0){
            int n=sc.nextInt();
            int []arr=new int[n];
            long sum=0L;
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
                sum+=arr[i];
            }
            int y=n*(n+1)/2;
            ArrayList<Integer> a=new ArrayList<>();
            boolean check=true;
            if(sum%y!=0){
                System.out.println("NO");
            }
            else{
                sum=sum/y;
                for(int i=0;i<n;i++){
                    int dif=0;
                    if(i==0){
                        dif=arr[0]-arr[n-1];

                    }
                    else{
                        dif=arr[i]-arr[i-1];
                    }
                    if((sum-dif)%n!=0 || sum-dif<=0){
                        System.out.println("NO");
                        check =false;
                        break;
                    }
                    else{
                        a.add((int)(sum-dif)/n);
                    }
                }
                if(check==true){
                    System.out.println("YES");
                    for(int i=0;i<n;i++){
                        System.out.print(a.get(i)+" ");
                    }
                    System.out.println();
                }
            }






            
            



            
            

        }
        

    }
    public static long gcd(long a,long b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }               
            
}
/////////////////////////////////////////////////////////////
//BINARY SEARCH
/*Arrays.binarySearch(arr,key);
if key--> present 
    return index
else 
    return -(index where it would be inserted)-1*/


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


/*  VALUE JUST GREATER THAN X  
 find_min(int[]arr,int x){
    int l=-1;
    int r=arr.length;
    while(r>l+1){
        int mid=(l+r)/2;
        if(arr[mid]<x){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return r;
 }
    VALUE JUST SMALLER THAN X
  find_max(int[]arr,int x){
    int l=-1;
    int r=arr.length;
    while(r>l+1){
        int mid=(l+r)/2;
        if(arr[mid]<=x){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return l;
 }  
   */ 
    
 


//////////////////////////////////////////////////////////////
// LCM AND GCD
/*
    public static int gcd(int a,int b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }
 
    public static int lcm(int a,int b){
         return (a / gcd(a, b)) * b;
    }*/


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

//Iterator



/*Iterator iterator = object.iterator();
 
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }*/
///////////////////////////////////////////////////////////////////////////////////


class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;
 
    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }
 
    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }
 
    public char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }
 
    public int nextInt() {
        return (int) nextLong();
    }
 
    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }
 
    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }
 
    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }
 
    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }
 
    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }
 
    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}

