Задачи
Фотострельба
Фотострельба
Фермер Джон выстроил $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$.
Входные данные #1
5 4 6 7 6
Выходные данные #1
3 1 5 2 4