Farmer John 正讓他的 $N$ 頭乳牛（$2\le N\le 10^3$）排隊拍照，乳牛編號為 $1\ldots N$。FJ 原本打算讓從左數第 $i$ 頭乳牛的編號為 $a_i,$，並將排列 $a_1,a_2,\ldots,a_N$ 寫在紙上。不幸的是，這張紙最近被 Farmer Nhoj 偷走了！

幸運的是，FJ 也許仍能恢復原先寫下的排列。在紙被偷走前，Bessie 記錄了序列 $b_1,b_2,\ldots,b_{N-1}$，對於每個 $1\le i<N.$，它滿足 $b_i=a_i+a_{i+1}$。

根據 Bessie 的資訊，幫助 FJ 恢復能夠產生 $b$ 的「字典序最小」的排列 $a$。如果存在某個 $j$，使得所有 $i<j$ 都滿足 $x_i=y_i$，且 $x_j<y_j$，則排列 $x$ 的字典序小於排列 $y$（也就是說，兩排列直到某個位置之前都相同，在該位置 $x$ 小於 $y$）。保證至少存在一個這樣的 $a$。

輸入格式

輸入第一行包含一個整數 $N.$。

第二行包含 $N-1$ 個以空格分隔的整數 $b_1,b_2,\ldots,b_{N-1}.$。

輸出格式

輸出一行，包含 $N$ 個以空格分隔的整數 $a_1,a_2,\ldots,a_{N}.$。

範例

輸入格式 1

5
4 6 7 6

輸出格式 1

3 1 5 2 4

說明

$a$ 產生 $b$，因為 $3+1=4$、$1+5=6$、$5+2=7$，且 $2+4=6.$。

子任務

• 測試點 $2$–$4$ 滿足 $N\le 8.$。

• 測試點 $5$–$10$ 沒有額外限制。

題目作者：Benjamin Qi 和 Chris Zhang