题目描述

农夫约翰在给他编号为 $1…N$的$N$头奶牛排队拍照。

约翰一开始计划从左向右数第 i 个位置排编号为 $a_i$的奶牛，他在一张纸上写下了排列$a_1,a_2,…,a_N$。

不幸的是，这张纸刚刚被小偷偷走了！

幸好约翰仍然有机会恢复他之前写下的排列。

在这张纸被偷走之前，奶牛贝茜记录了序列 $b_1,b_2,…,b_{N−1}$，对于每一个 $1≤i<N$ 满足 $b_i=a_i+a_{i+1}$。

基于贝茜的信息，帮助约翰恢复可以产生序列 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$。

样例输入

5
4 6 7 6

样例输出

3 1 5 2 4

提示

$2≤N≤10^3$

$a$ 能够产生 $b$，因为 3+1=4，1+5=6，5+2=7，2+4=6。