题目描述

小书童在做题。为了缓解做题的疲惫，他做了一个有趣的游戏。他把编号为 1…N 的 N 个题目重新排序，并计划按照排好的顺序刷题。从左向右数第 i 个位置排编号为 ai 的题目，他在一张纸上写下了排列 a1，a2，…，aN。不幸的是，这张纸被他丢掉了！幸好小书童仍然有机会恢复他之前写下的排列。在这张纸丢失之前，他记录了序列 b1，b2，…，bN−1，对于每一个 1 ≤ i < N 满足 b[i] = a[i] + a[i+1]。基于序列b的信息，帮助小书童恢复可以产生序列 b 的"字典序最小"的排列 a。排列 x 字典序小于排列 y：如果对于某个 j，对于所有 i < j 均有 xi = yi，且有 xj < yj（换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y）。保证存在至少一个满足条件的 a。

输入格式

输入的第一行包含一个整数N。 第二行包含N−1个空格分隔的整数 b1,b2,…,bN−1。

输出格式

   输出一行，包含N个空格分隔的整数 a1,a2,…,aN。

样例

input

5
4 6 7 6

output

3 1 5 2 4

提示

3+1=4, 1+5=6, 5+2=7, 2+4=6.

数据范围

n<=1000,b_i<1000