Обсуждая подходящую задачу A для раунда на Codeforces, Костя создал циклический массив из целых положительных чисел \(a_1, a_2, \ldots, a_n\). Так как разговор затянулся, Костя создал новый циклический массив \(b_1, b_2, \ldots, b_{n}\) такой, что \(b_i = (a_i \mod a_{i + 1})\), где мы считаем \(a_{n+1} = a_1\). Под \(mod\) имеется ввиду остаток от деления. Когда разговор стал интересным, Костя абсолютно забыл массив \(a\). Вдруг он подумал, что восстановление массива \(a\) из массива \(b\) может быть интересной задачей (к сожалению, не A).
Выходные данные
Если возможно восстановить некоторый массив \(a\) длины \(n\) такой, что \(b_i = a_i \mod a_{(i \mod n) + 1}\) выполняется для всех \(i = 1, 2, \ldots, n\), выведите «YES» в первой строчке и числа \(a_1, a_2, \ldots, a_n\) во второй строчке. Все \(a_i\) должны быть \(1 \le a_i \le 10^{18}\). Гарантируется, что если ответ существует, также существует ответ с данным ограниением.
Если невозможно восстановить никакой массив \(a\), выведите «NO» в первой строчке.
Вы можете выводить каждую букву в любом регистре: заглавной или строчной.
Примечание
В первом примере:
- \(1 \mod 3 = 1\)
- \(3 \mod 5 = 3\)
- \(5 \mod 2 = 1\)
- \(2 \mod 1 = 0\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3 1 0
|
YES
1 3 5 2
|
|
2
|
2
4 4
|
NO
|