Farmer John dispone in fila le sue $N$ mucche ($2\le N\le 10^3$), numerate $1\ldots N$, per un servizio fotografico. FJ voleva che la $i$-esima da sinistra fosse quella con numero $a_i,$ e ha scritto la permutazione $a_1,a_2,\ldots,a_N$ su un foglio. Purtroppo Farmer Nhoj ha rubato quel foglio di recente!
Fortunatamente, FJ potrebbe ancora recuperare la permutazione scritta. Prima del furto, Bessie ha annotato la sequenza $b_1,b_2,\ldots,b_{N-1}$ che soddisfa $b_i=a_i+a_{i+1}$ per ogni $1\le i<N.$
Dalle informazioni di Bessie, aiuta FJ a recuperare la permutazione $a$ «lessicograficamente minima» che potrebbe aver prodotto $b$. Una permutazione $x$ è lessicograficamente minore di $y$ se per qualche $j$, $x_i=y_i$ per ogni $i<j$ e $x_j<y_j$ (sono identiche fino a un certo punto, dove $x$ è minore di $y$). È garantita l’esistenza di almeno una tale $a$.
Input
La prima riga contiene un intero $N.$
La seconda contiene $N-1$ interi $b_1,b_2,\ldots,b_{N-1}.$ separati da spazi.
Output
Una riga con $N$ interi $a_1,a_2,\ldots,a_{N}.$ separati da spazi.
Esempi
Input 1
5 4 6 7 6
Output 1
3 1 5 2 4
Nota
$a$ produce $b$ perché $3+1=4$, $1+5=6$, $5+2=7$ e $2+4=6.$
Punteggio
I casi $2$–$4$ soddisfano $N\le 8.$
I casi $5$–$10$ non hanno vincoli aggiuntivi.
Autori del problema: Benjamin Qi e Chris Zhang