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 记录了序列 b_1,b_2,\ldots,b_{N-1}，对于每一个 1\le i < N 满足 b_i=a_i+a_{i+1}。

基于 Bessie 的信息，帮助 FJ 恢复可以产生序列 b 的“字典序最小”的排列 a。排列 x 字典序小于排列 y，如果对于某个 j，对于所有 i < j 均有 x_i = y_i，且有 x_j < y_j（换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y）。保证存在至少一个满足条件的 a。

测试点性质：

• 测试点 2-4 满足 N\le 8。
• 测试点 5-10 没有额外限制。

输入的第一行包含一个整数 N。

第二行包含 N-1 个空格分隔的整数 b_1,b_2,\ldots,b_{N-1}。

输出一行，包含 N 个空格分隔的整数 a_1,a_2,\ldots,a_{N}。

【样例解释】

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