eolymp
bolt
Try our new interface for solving problems
Problems

Обратный сбор бобов

Обратный сбор бобов

Time limit 1 second
Memory limit 64 MiB

Как мы уже говорили в предыдущей задаче, Петя очень любит игру с горошинами. Игра заключается в том, что имеется N чаш, расставленных по кругу, и некоторое количество горошин в каждой из них. Каждый ход он берет все горошины из некоторой чаши и последовательно кладет их по одной в каждую последующую чашу. На первом ходу используются горошины из первой чаши, а в дальнейшем из той, в которую была помещена последняя горошина на предыдущем шаге. Выполнив несколько таких ходов, Петя получил состояние, в котором вновь должен брать горошины из первой чаши. Но теперь он задумался о том, какая же позиция была ходом ранее.

Input data

В первой строке входного файла задается количество чаш N (1N10^5). Во второй строке записаны N чисел a_i, определяющие количества горошин в соответствующих чашах (0a_i10^9, a_1 = 0) в текущем состоянии.

Output data

В единственную строку выходного файла необходимо вывести N чисел - количества горошин в соответствующих чашах в предыдущий ход. Если существует несколько вариантов предыдущего состояния, можно выводить любое из них. Если таких состояний не существует, выведите одно число −1.

Examples

Input example #1
8
1 0 3 0 0 3 2 3
Output example #1
0 0 3 0 4 2 1 2
Author Виталий Неспирный
Source Летняя школа Севастополь 2013, Волна 2, День 4