\(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\) или скажите, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите ответ следующим образом:
Если не существует подходящей последовательности \(a\), выведите NO. Иначе, в первой строке выведете YES, в следующей строке выведите последовательность \(a_1, a_2, \dots, a_n\) из \(n\) целых чисел, где \(a_i\) (\(1 \le a_i \le 10^{9}\)) — начальная длительность репертуара \(i\)-го певца. Если ответов несколько — выведите любой из них.
Примечание
Рассмотрим \(1\)-й набор входных данных примера:
- \(1\)-й певец в \(1\)-м городе даст концерт на \(3\) минуты, во \(2\)-м — на \(6\) минут, в \(3\)-м — на \(9\) минут;
- \(2\)-й певец в \(1\)-м городе даст концерт на \(3\) минуты, во \(2\)-м — на \(1\) минуту, в \(3\)-м — на \(2\) минуты;
- \(3\)-й певец в \(1\)-м городе даст концерт на \(6\) минут, во \(2\)-м — на \(9\) минут, в \(3\)-м — на \(3\) минуты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|