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