Farmer John aligne ses $N$ vaches ($2\le N\le 10^3$), numérotées $1\ldots N$, pour une séance photo. FJ voulait que la $i$-ème vache depuis la gauche porte le numéro $a_i,$ et a écrit la permutation $a_1,a_2,\ldots,a_N$ sur une feuille. Malheureusement, Farmer Nhoj a récemment volé cette feuille !
Heureusement, FJ pourrait encore reconstituer la permutation écrite. Avant le vol, Bessie a noté la suite $b_1,b_2,\ldots,b_{N-1}$ vérifiant $b_i=a_i+a_{i+1}$ pour chaque $1\le i<N.$
À partir des informations de Bessie, aidez FJ à reconstituer la permutation $a$ « minimale lexicographiquement » qui aurait pu produire $b$. Une permutation $x$ est lexicographiquement plus petite que $y$ si, pour un certain $j$, $x_i=y_i$ pour tout $i<j$ et $x_j<y_j$ (elles sont donc identiques jusqu’à un certain point, où $x$ est plus petite que $y$). Au moins une telle $a$ existe.
Entrée
La première ligne contient un entier $N.$
La deuxième contient $N-1$ entiers $b_1,b_2,\ldots,b_{N-1}.$ séparés par des espaces.
Sortie
Une ligne contenant $N$ entiers $a_1,a_2,\ldots,a_{N}.$ séparés par des espaces.
Exemples
Entrée 1
5 4 6 7 6
Sortie 1
3 1 5 2 4
Remarque
$a$ produit $b$ car $3+1=4$, $1+5=6$, $5+2=7$ et $2+4=6.$
Sous-tâches
Les tests $2$–$4$ vérifient $N\le 8.$
Les tests $5$–$10$ n’ont aucune contrainte supplémentaire.
Auteurs du problème : Benjamin Qi et Chris Zhang