← 返回题目列表

Codeforces · 1618/E

E. 歌手巡演

中文机器翻译题面 查看原题

$$$n$$$ 城镇按顺序排列成圆圈。城镇按顺时针顺序从 $$$1$$$ 到 $$$n$$$ 编号。在第 $$$i$$$ 个城镇中,住着一位歌手,其曲目为 [1, n]$$$ 中每个 $$$i \$$$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$$$ 个城镇的音乐会总持续时间。重建任何正确的正整数序列 $$$a$$$ 或者说这是不可能的。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^3$$$) — 测试用例的数量。然后是测试用例。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^4$$$) — 城市数量。第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{9}$$$) — 第 $$$i$$$ 个城市的音乐会总持续时间。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印答案如下:

如果没有合适的序列$$$a$$$,则打印NO。否则,在第一行打印 YES,在下一行打印 $$$n$$$ 整数的序列 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) 是第 $$$i$$$ 歌手曲目的初始持续时间。如果有多个答案,请打印其中任何一个。

示例

输入 #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

注意

让我们考虑示例的 $$$1$$$-st 测试用例:

1. $$$1$$$-st 城市的 $$$1$$$-st 歌手将举办音乐会 $$$3$$$ 分钟,在 $$$2$$$-nd — $$$6$$$ 分钟,在 $$$3$$$-rd — $$$9$$$ 分钟;
2. $$$1$$$-st 城市的第 $$$2$$$-nd 歌手将举办一场音乐会 $$$3$$$ 分钟,在 $$$2$$$-nd - $$$1$$$ 分钟,在 $$$3$$$-rd - $$$2$$$ 分钟;
3. $$$1$$$-st 城市的 $$$3$$$-rd 歌手将举办一场音乐会,音乐会时间为 $$$6$$$ 分钟,在 $$$2$$$-nd 举行音乐会 $$$9$$$ 分钟,在 $$$3$$$-rd 举办音乐会 $$$3$$$ 分钟。