Singers' Tour

题意翻译

$n$ 个城镇依次排列成一个圆圈，按顺时针从 $1$ 到 $n$ 编号。在第 $i$ 个镇中有一个歌手，Ta起初只会演奏一首长度为整数 $a_i$ 的曲子。 每位歌手从他居住的城镇开始，按顺时针顺序依次访问所有 $n$ 个城镇，并在每个城镇举办恰好一场音乐会。此外，在每个城镇，第 $i$ 个歌手都得到灵感，创作了一首长度 $a_i$ 分钟的歌曲。这首歌被添加到他的曲目中，并在后来的所有城市被演奏。 因此，对于第 $i$ 个歌手，在第 $i$ 个城镇的音乐会将持续 $a_i$ 分钟，在第 $(i + 1)$ 个城镇的音乐会将持续 $2 \cdot a_i$ 分钟, ..., 在第 $((i + k) \bmod n + 1)$ 个城镇的音乐会将持续 $(k + 2) \cdot a_i$ , ..., 在第 $((i + n - 2) \bmod n + 1)$个城镇的音乐会将持续 $n \cdot a_i$ 分钟。 给定一个 $b$ 整数数组，其中 $b_i$ 是第 $i$ 个城镇的所有音乐会的总时长。如果可以根据 $b$ 恢复序列 $a$ ，则输出`YES`和任意正确的 $a$。否则输出`NO`。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5

说明

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.