E. Турне певцов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ городов последовательно расположены на окружности. Города пронумерованы от $$$1$$$ до $$$n$$$ в порядке по часовой стрелке. В $$$i$$$-м городе живет певец с репертуаром на $$$a_i$$$ минут для каждого $$$i \in [1, n]$$$.

Каждый певец двигался по окружности в порядке по часовой стрелке и дал ровно один концерт в каждом из $$$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, в следующей строке выведите последовательность $$$a_1, a_2, \dots, a_n$$$ из $$$n$$$ целых чисел, где $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) — начальная длительность репертуара $$$i$$$-го певца. Если ответов несколько — выведите любой из них.

Пример
Входные данные
4
3
12 16 14
1
1
3
1 2 3
6
81 75 75 93 93 87
Выходные данные
YES
3 1 3 
YES
1 
NO
YES
5 5 4 1 4 5
Примечание

Рассмотрим $$$1$$$-й набор входных данных примера:

  • $$$1$$$-й певец в $$$1$$$-м городе даст концерт на $$$3$$$ минуты, во $$$2$$$-м — на $$$6$$$ минут, в $$$3$$$-м — на $$$9$$$ минут;
  • $$$2$$$-й певец в $$$1$$$-м городе даст концерт на $$$3$$$ минуты, во $$$2$$$-м — на $$$1$$$ минуту, в $$$3$$$-м — на $$$2$$$ минуты;
  • $$$3$$$-й певец в $$$1$$$-м городе даст концерт на $$$6$$$ минут, во $$$2$$$-м — на $$$9$$$ минут, в $$$3$$$-м — на $$$3$$$ минуты.