Фотострельба

Фермер Джон выстроил $n$ своих коров, пронумерованных $\mathrm{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$.

Входные данные

Первая строка содержит одно целое число $n(2\le n\le 10^3)$. Вторая строка содержит $n-1$ целых чисел $b_1,b_2,...,b_{n-1}$.

Выходные данные

Выведите лексикографически минимальную перестановку $a_1,a_2,...,a_n$.

Примеры

Примечание

$a$ производит $b$ потому что $3+1=4$, $1+5=6$, $5+2=7$ и $2+4=6$.