Массив целых чисел \(p_1, p_2, \dots, p_n\) называется перестановкой, если он содержит каждое число от \(1\) до \(n\) ровно один раз. Например, следующие массивы являются перестановками: \([3, 1, 2]\), \([1]\), \([1, 2, 3, 4, 5]\) и \([4, 3, 1, 2]\). Следующие массивы перестановками не являются: \([2]\), \([1, 1]\), \([2, 3, 4]\).
Поликарп изобрел невероятно крутую перестановку \(p_1, p_2, \dots, p_n\) длины \(n\). К сожалению, он забыл эту перестановку. Единственное, что он помнит, это массив \(q_1, q_2, \dots, q_{n-1}\) длины \(n-1\), где \(q_i=p_{i+1}-p_i\).
Заданы \(n\) и \(q=q_1, q_2, \dots, q_{n-1}\), помогите Поликарпу по этой информации восстановить придуманную им перестановку.
Выходные данные
Выведите -1, если перестановки длины \(n\), которая соответствует массиву \(q\), не существует. В противном случае выведите \(p_1, p_2, \dots, p_n\). Если существует несколько подходящих перестановок, то выведите любую из них.