Farmer John ustawia swoje $N$ krów ($2\le N\le 10^3$), ponumerowanych $1\ldots N$, do zdjęcia. FJ planował, by $i$-ta krowa od lewej miała numer $a_i,$, i zapisał permutację $a_1,a_2,\ldots,a_N$ na kartce. Niestety niedawno Farmer Nhoj ukradł kartkę!

Na szczęście FJ może jeszcze odtworzyć zapisaną permutację. Przed kradzieżą Bessie zanotowała ciąg $b_1,b_2,\ldots,b_{N-1}$ spełniający $b_i=a_i+a_{i+1}$ dla każdego $1\le i<N.$

Na podstawie informacji Bessie pomóż FJ odtworzyć „leksykograficznie najmniejszą” permutację $a$, która mogła dać $b$. Permutacja $x$ jest leksykograficznie mniejsza od $y$, jeśli dla pewnego $j$ zachodzi $x_i=y_i$ dla wszystkich $i<j$ oraz $x_j<y_j$ (są więc identyczne do pewnego miejsca, w którym $x$ jest mniejsza od $y$). Istnieje co najmniej jedna taka $a$.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $N.$

Drugi zawiera $N-1$ liczb całkowitych $b_1,b_2,\ldots,b_{N-1}.$ oddzielonych spacjami.

Wyjście

Jeden wiersz z $N$ liczbami całkowitymi $a_1,a_2,\ldots,a_{N}.$ oddzielonymi spacjami.

Przykład

Wejście 1

5
4 6 7 6

Wyjście 1

3 1 5 2 4

Uwagi

$a$ daje $b$, ponieważ $3+1=4$, $1+5=6$, $5+2=7$ i $2+4=6.$

Podzadania

• Testy $2$–$4$ spełniają $N\le 8.$

• Testy $5$–$10$ nie mają dodatkowych ograniczeń.

Autorzy zadania: Benjamin Qi i Chris Zhang