Maximums

Alicia has an array, a_1, a_2, …, a_n, of non-negative integers. For each 1 ≤ i ≤ n, she has found a non-negative integer x_i = max(0, a_1, …, a_{i-1}). Note that for i=1, x_i = 0.

For example, if Alicia had the array a = {0, 1, 2, 0, 3}, then x = {0, 0, 1, 2, 2}.

Then, she calculated an array, b_1, b_2, …, b_n: b_i = a_i - x_i.

For example, if Alicia had the array a = {0, 1, 2, 0, 3}, b = {0-0, 1-0, 2-1, 0-2, 3-2} = {0, 1, 1, -2, 1}.

Alicia gives you the values b_1, b_2, …, b_n and asks you to restore the values a_1, a_2, …, a_n. Can you help her solve the problem?

Input

The first line contains one integer n (3 ≤ n ≤ 200 000) – the number of elements in Alicia's array.

The next line contains n integers, b_1, b_2, …, b_n (-10^9 ≤ b_i ≤ 10^9).

It is guaranteed that for the given array b there is a solution a_1, a_2, …, a_n, for all elements of which the following is true: 0 ≤ a_i ≤ 10^9.

Output

Print n integers, a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9), such that if you calculate x according to the statement, b_1 will be equal to a_1 - x_1, b_2 will be equal to a_2 - x_2, ..., and b_n will be equal to a_n - x_n.

It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

Examples

Input

5 0 1 1 -2 1

Output

0 1 2 0 3

Input

3 1000 999999000 -1000000000

Output

1000 1000000000 0

Input

5 2 1 2 2 3

Output

2 3 5 7 10

Note

The first test was described in the problem statement.

In the second test, if Alicia had an array a = {1000, 1000000000, 0}, then x = {0, 1000, 1000000000} and b = {1000-0, 1000000000-1000, 0-1000000000} = {1000, 999999000, -1000000000}.

inputFormat

Input

The first line contains one integer n (3 ≤ n ≤ 200 000) – the number of elements in Alicia's array.

The next line contains n integers, b_1, b_2, …, b_n (-10^9 ≤ b_i ≤ 10^9).

It is guaranteed that for the given array b there is a solution a_1, a_2, …, a_n, for all elements of which the following is true: 0 ≤ a_i ≤ 10^9.

outputFormat

Output

Print n integers, a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9), such that if you calculate x according to the statement, b_1 will be equal to a_1 - x_1, b_2 will be equal to a_2 - x_2, ..., and b_n will be equal to a_n - x_n.

It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

Examples

Input

5 0 1 1 -2 1

Output

0 1 2 0 3

Input

3 1000 999999000 -1000000000

Output

1000 1000000000 0

Input

5 2 1 2 2 3

Output

2 3 5 7 10

Note

The first test was described in the problem statement.

In the second test, if Alicia had an array a = {1000, 1000000000, 0}, then x = {0, 1000, 1000000000} and b = {1000-0, 1000000000-1000, 0-1000000000} = {1000, 999999000, -1000000000}.

样例

3
1000 999999000 -1000000000

1000 1000000000 0

</p>