Фермер Джон выстроил n своих коров, пронумерованных 1...n, для фотоснимка. Изначально ФД планировал, что i-ая корова слева будет корова с номером ai, и выписал перестановку a1,a2,...,an на листке бумаги. К несчастью этот листок украл фермер Нхож.
Однако, ФД сможет восстановить перестановку, которую он изначально выписал. Перед тем, как листок с перестановкой был украден, Бесси выписала последовательность b1,b2,...,bn−1 такую, что bi=ai+ai+1 для всех i(1≤i<n).
Основываясь на информации от Бесси, помогите ФД восстановить "лексикографически минимальную" перестановку a, которая может произвести b. Перестановка x лексикографически меньше перестановки y, если для некоторого j, xi=yi для всех i<j и xj<yj (другими словами, две перестановки идентичны до определённой точки, в которой x меньше чем y). Гарантируется, что существует как минимум одна такая перестановка a.
Первая строка содержит одно целое число n(2≤n≤103). Вторая строка содержит n−1 целых чисел b1,b2,...,bn−1.
Выведите лексикографически минимальную перестановку a1,a2,...,an.
a производит b потому что 3+1=4, 1+5=6, 5+2=7 и 2+4=6.