Фермер Джон выстроил $n$ своих коров, пронумерованных $1 ... n$, для фотоснимка. Изначально ФД планировал, что $i$-ая корова слева будет корова с номером $a_i$, и выписал перестановку $a_1, a_2, ..., a_n$ на листке бумаги. К несчастью этот листок украл фермер Нхож. Однако, ФД сможет восстановить перестановку, которую он изначально выписал. Перед тем, как листок с перестановкой был украден, Бесси выписала последовательность $b_1, b_2, ..., b_{n-1}$ такую, что $b_i = a_i + a_{i+1}$ для всех $i\:(1 \le i < n)$. Основываясь на информации от Бесси, помогите ФД восстановить "лексикографически минимальную" перестановку $a$, которая может произвести $b$. Перестановка $x$ лексикографически меньше перестановки $y$, если для некоторого $j$, $x_i = y_i$ для всех $i < j$ и $x_j < y_j$ (другими словами, две перестановки идентичны до определённой точки, в которой $x$ меньше чем $y$). Гарантируется, что существует как минимум одна такая перестановка $a$. \InputFile Первая строка содержит одно целое число $n\:(2 \le n \le 10^3)$. Вторая строка содержит $n - 1$ целых чисел $b_1, b_2, ..., b_{n-1}$. \OutputFile Выведите лексикографически минимальную перестановку $a_1, a_2, ..., a_n$. \Note $a\:$ производит $b$ потому что $3 + 1 = 4$, $1 + 5 = 6$, $5 + 2 = 7$ и $2 + 4 = 6$.