题目描述

Farmer John 在给他编号为 1~N 的 N头奶牛排队拍照（ 2 ≤ N ≤ $10^3$ ）。 John 一开始计划从左向右数第 i 个位置排编号为 $a_i$ 的奶牛，他在一张纸上写下了排列 $a_1,a_2,...,a_N$ 。不幸的是，这张纸刚刚被 Farmer NHOJ 偷走了！

幸好 John 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前， Bessie 记录了序列 $b_1,b_2,...,b_{N−1}$，对于每一个 $b_i$ ( 1 ≤ 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≤8。

• 测试点 5-10 没有额外限制。

输入格式

第一行包含一个整数 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

样例解释

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