Farmer John is arranging his n cows numbered 1...n for a photoshoot. Initially, FJ planned for the i-th cow from the left to be the cow numbered ai, and wrote down the permutation a1,a2,...,an on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!
Fortunately, there might still be a chance for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence b1,b2,...,bn−1, which satisfies bi=ai+ai+1 for each i (1≤i<n).
Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation a that could have produced b. A permutation x is lexicographically smaller than a permutation y if for some j, xi=yi for all i<j and xj<yj (in other words, the two permutations are identical up to a certain point, at which x is smaller than y). It is guaranteed that at least one such a exists.
The first line contains a single integer n (2≤n≤103). The second line contains n−1 integers b1,b2,...,bn−1.
Print the lexicographically minimum permutation a1,a2,...,an.
a produces b because 3+1=4, 1+5=6, 5+2=7 and 2+4=6.