Problem Description

Farmer John is lining up $N$ cows numbered $1\ldots N$ to take a photo ($2\le N\le 10^3$). FJ originally planned that the cow with number $a_i$ would stand in the $i$-th position from left to right, so he wrote down the permutation $a_1,a_2,\ldots,a_N$ on a sheet of paper. Unfortunately, this sheet of paper has just been stolen by Farmer Nhoj!

Luckily, FJ still has a chance to recover the permutation he wrote earlier. Before the paper was stolen, Bessie recorded a sequence $b_1,b_2,\ldots,b_{N-1}$, where for each $1\le i<N$, we have $b_i=a_i+a_{i+1}$.

Based on Bessie's information, help FJ recover the lexicographically smallest permutation $a$ that can produce the sequence $b$. A permutation $x$ is lexicographically smaller than a permutation $y$ if there exists some $j$ such that for all $i<j$, $x_i=y_i$, and $x_j<y_j$ (in other words, the two permutations are the same up to some position, and at that position $x$ is smaller than $y$). It is guaranteed that at least one valid $a$ exists.

Input Format

The first line contains an integer $N$.

The second line contains $N-1$ space-separated integers $b_1,b_2,\ldots,b_{N-1}$.

Output Format

Output one line containing $N$ space-separated integers $a_1,a_2,\ldots,a_N$.

5
4 6 7 6

3 1 5 2 4

Hint

Sample Explanation 1

The sequence $a$ can produce $b$ because $3+1=4$, $1+5=6$, $5+2=7$, $2+4=6$.

Test Point Properties

• Test points $2-4$ satisfy $N\le 8$.
• Test points $5-10$ have no additional constraints.

Translated by ChatGPT 5