Lexicographically Smallest Cow Lineup

Farmer John has N cows numbered from \(1\) to \(N\) (where \(2 \le N \le 10^3\)) lined up for a photo. Initially, he planned to arrange the cows so that the cow in the \(i\)th position (from left to right) had the number \(a_i\), and he wrote down the permutation \(a_1, a_2, \ldots, a_N\). However, the paper containing this permutation was stolen by Farmer Nhoj!

Fortunately, before the theft, Bessie recorded the sequence \(b_1, b_2, \ldots, b_{N-1}\) where for each \(1 \le i < N\), \(b_i = a_i + a_{i+1}\). Based on Bessie's notes, help FJ recover a permutation \(a\) which can produce the sequence \(b\), and among all valid permutations, output the lexicographically smallest one.

A permutation \(x\) is lexicographically smaller than a permutation \(y\) if at the first index \(j\) where they differ, \(x_j < y_j\) (i.e. they are identical up to some index and then \(x_j\) is smaller).

Note: It is guaranteed that there exists at least one valid permutation \(a\) for the given \(b\).

Mathematical formulation:

For a valid permutation \(a = (a_1, a_2, \ldots, a_N)\), the following must hold for every \(1 \le i < N\):

\[ a_i + a_{i+1} = b_i, \quad 1 \le i

inputFormat

The first line contains one integer \(N\) (\(2 \le N \le 10^3\)).

The second line contains \(N-1\) integers \(b_1, b_2, \ldots, b_{N-1}\) separated by spaces.

outputFormat

Output \(N\) space-separated integers representing the lexicographically smallest permutation \(a\) that can produce the sequence \(b\).

sample

4
5 7 5

1 4 3 2