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

Фермер Джон вишикував $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$ $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$.