$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 \in [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 \cdot a_i$ minutes, ..., in the $((i + k) \bmod n + 1)$-th town the duration of the concert will be $(k + 2) \cdot a_i$, ..., in the town $((i + n - 2) \bmod n + 1)$ — $n \cdot 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.

The first line contains one integer $t$ $(1 \le t \le 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 \le n \le 4 \cdot 10^4$) — the number of cities. The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^{9}$) — the total duration of concerts in $i$-th city.

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

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, \dots, a_n$ of $n$ integers, where $a_i$ ($1 \le a_i \le 10^{9}$) is the initial duration of repertoire of the $i$-th singer. If there are multiple answers, print any of them.