Farmer John stellt seine $N$ Kühe ($2\le N\le 10^3$) mit Nummern $1\ldots N$ für ein Fotoshooting auf. FJ plante, dass die $i$-te Kuh von links die Nummer $a_i,$ trägt, und schrieb die Permutation $a_1,a_2,\ldots,a_N$ auf ein Blatt. Leider hat Farmer Nhoj dieses Blatt kürzlich gestohlen!

Zum Glück könnte FJ die aufgeschriebene Permutation noch rekonstruieren. Vor dem Diebstahl notierte Bessie die Folge $b_1,b_2,\ldots,b_{N-1}$ mit $b_i=a_i+a_{i+1}$ für jedes $1\le i<N.$

Hilf FJ anhand von Bessies Angaben, die „lexikografisch kleinste“ Permutation $a$ zu rekonstruieren, die $b$ erzeugt haben könnte. Eine Permutation $x$ ist lexikografisch kleiner als $y$, wenn für ein $j$ gilt: $x_i=y_i$ für alle $i<j$ und $x_j<y_j$ (sie stimmen also bis zu einer Stelle überein, an der $x$ kleiner als $y$ ist). Mindestens eine solche $a$ existiert garantiert.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N.$

Die zweite enthält $N-1$ durch Leerzeichen getrennte ganze Zahlen $b_1,b_2,\ldots,b_{N-1}.$

Ausgabe

Eine Zeile mit $N$ durch Leerzeichen getrennten ganzen Zahlen $a_1,a_2,\ldots,a_{N}.$

Beispiele

Eingabe 1

5
4 6 7 6

Ausgabe 1

3 1 5 2 4

Hinweis

$a$ erzeugt $b$, weil $3+1=4$, $1+5=6$, $5+2=7$ und $2+4=6.$

Teilaufgaben

• Testfälle $2$–$4$ erfüllen $N\le 8.$

• Testfälle $5$–$10$ haben keine weiteren Einschränkungen.

Autoren der Aufgabe: Benjamin Qi und Chris Zhang