5004 - 拍照

通过次数

22

提交次数

58

时间限制 : 1 秒
内存限制 : 128 MB

Farmer John 在给他编号为 1\ldots NN 头奶牛排队拍照(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}

样例

输入

5
4 6 7 6

输出

3 1 5 2 4

提示

【样例解释】

a 能够产生 b,因为 3+1=41+5=65+2=72+4=6

来源

USACO 2020 January Contest, Bronze Problem 2. Photoshoot