Singers' Tour
Contest: Codeforces Round 760 (Div. 3)
Difficulty rating: 1700
Tags: constructive algorithms, math

$$$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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

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

Example output:
YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5

Editorial:
First, $$$b_i = a_i + 2 \cdot a_{i - 1} + \dots + i \cdot a_1 + (i + 1) \cdot a_n + \dots n \cdot a_{i + 1}$$$.
Consider the sum $$$b_1 + b_2 + \cdots + b_n$$$. If we substitute the formula of $$$b_i$$$ then for every $$$i = 1, 2, \dots, n$$$ the coefficient at $$$a_i$$$ will be equal to $$$\frac{n \cdot (n + 1)}{2}$$$, so we can find the sum $$$S$$$ of all $$$a_i$$$: $$$S = a_1 + a_2 + \dots + a_n$$$ is equal to $$$\frac{2 \cdot (b_1 + b_2 + \dots + b_n)}{n \cdot (n + 1)}$$$. If the sum of $$$b_i$$$ isn't divisible by $$$\frac{n \cdot (n + 1)}{2}$$$, then the answer is NO.
Now let's consider the difference between two neighboring towns: $$$b_i - b_{(i + n - 2) \mod n + 1} = a_{i - 1} + a_{i - 2} + \dots + a_{i \mod n + 1} - (n - 1) \cdot a_i = S - a_i - (n - 1) \cdot a_i = S - n \cdot a_i$$$, so $$$a_i = \frac{S - b_i + b_{(i + n - 2) \mod n + 1}}{n}$$$. If the value of $$$a_i$$$ we found isn't a positive integer, then the answer if NO. Otherwise, we can find a single value of $$$a_i$$$ for every $$$i = 1, 2, \dots n$$$. It's easy to see that these values are correct.
Overall complexity: $$$O(n)$$$ per testcase.