题目描述

小 Z 原来在纸上写了一个含有 $1$ 到 $N$ 共 $N$ 个元素的序列，里面的元素分别是$a_1,a_2,…,a_N$，不巧的是这时候吹来了一阵风，把这张纸给吹走了。

但还好小Z留了一手，记下了序列 $b_1,b_2,…,b_{N−1}$，对于每一个序列中的第 $i$ 个数，满足 $b_i=a_i+a_{i+1}$。

现在小 Z 希望你能根据 $b$ 序列，帮助他恢复原有的 $a$ 序列。若有多种答案，选择其中字典序最小的排列。

• 排列 $x$ 字典序小于排列 $y$，如果对于某个 $j$，对于所有 $i<j$ 均有 $x_i=y_i$，且有 $x_j<y_j$（换句话说，这两个排列到某个位置之前都相同，在这个位置上 $x$ 小于 $y$）。保证存在至少一个满足条件的 $a$。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N−1$ 个空格分隔的整数 $b_1,b_2,…,b_{N−1}$。

输出格式

输出一行，包含 $N$ 个空格分隔的整数 $a_1,a_2,…,a_N$。

样例 #1

样例输入 #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$。

【数据范围】

• 对于$50\%$的数据，满足 $2 \le N \le 8$。
• 对于$100\%$的数据，满足$2 \le N \le 10^3$。