Farmer John alinha suas $N$ vacas ($2\le N\le 10^3$), numeradas $1\ldots N$, para uma sessão de fotos. FJ pretendia que a $i$-ésima vaca a partir da esquerda fosse a de número $a_i,$ e escreveu a permutação $a_1,a_2,\ldots,a_N$ numa folha. Infelizmente, Farmer Nhoj roubou essa folha recentemente!

Felizmente, FJ talvez ainda consiga recuperar a permutação escrita. Antes do roubo, Bessie anotou a sequência $b_1,b_2,\ldots,b_{N-1}$ que satisfaz $b_i=a_i+a_{i+1}$ para cada $1\le i<N.$

Com as informações de Bessie, ajude FJ a recuperar a permutação $a$ «lexicograficamente mínima» que poderia produzir $b$. Uma permutação $x$ é lexicograficamente menor que $y$ se, para algum $j$, $x_i=y_i$ para todo $i<j$ e $x_j<y_j$ (elas são idênticas até certo ponto, onde $x$ é menor que $y$). É garantido que existe pelo menos uma $a$ assim.

Entrada

A primeira linha contém um inteiro $N.$

A segunda contém $N-1$ inteiros $b_1,b_2,\ldots,b_{N-1}.$ separados por espaços.

Saída

Uma linha com $N$ inteiros $a_1,a_2,\ldots,a_{N}.$ separados por espaços.

Exemplos

Entrada 1

5
4 6 7 6

Saída 1

3 1 5 2 4

Nota

$a$ produz $b$ porque $3+1=4$, $1+5=6$, $5+2=7$ e $2+4=6.$

Pontuação

• Os casos $2$–$4$ satisfazem $N\le 8.$

• Os casos $5$–$10$ não têm restrições adicionais.

Autores do problema: Benjamin Qi e Chris Zhang