Classical Hard Permutation Problem

A permutation of length $n$ is an array $p$ = [ $p_1, p_2, \ldots, p_n$ ], which contains every integer from $1$ to $n$ (inclusive) and, moreover, each number appears exactly once.

$\mathbb{Mr. \ COACH}$ gives you the following problem:

Given $d_i = p_{i+1} - p_i$ for each $i$ ($1 \le i \le n-1$) can you find the permutation $p$?

Input

The first line contains a single integer $n$ ($1 \le n \le 10^6$) – the length of the permutation $p$

The second line contains $n-1$ integers $d_1, d_2, \ldots, d_{n-1}$ ($d_i = p_{i+1} - p_i$).

Output

Print the hidden permutation $p$

Example 1

stdin

3
-1 -1

stdout

3 2 1

Example 2

stdin

5
-3 1 -2 3

stdout

5 2 3 1 4