Farmer John は $1\ldots N$ の番号が付いた $N$ 頭の牛（$2\le N\le 10^3$）を写真撮影のために並べています。FJ は当初、左から $i$ 番目を番号 $a_i,$ の牛にする予定で、順列 $a_1,a_2,\ldots,a_N$ を紙に書きました。残念ながら、この紙は最近 Farmer Nhoj に盗まれました！

幸い、FJ は元の順列を復元できるかもしれません。紙が盗まれる前に、Bessie は各 $1\le i<N.$ に対して $b_i=a_i+a_{i+1}$ を満たす列 $b_1,b_2,\ldots,b_{N-1}$ を記録しました。

Bessie の情報から、$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

注記

$3+1=4$、$1+5=6$、$5+2=7$、$2+4=6.$ なので、$a$ は $b$ を生成します。

小課題

• テストケース $2$–$4$ は $N\le 8.$ を満たします。

• テストケース $5$–$10$ に追加の制約はありません。

問題作成者：Benjamin Qi と Chris Zhang