Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Maximums

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlicia has an array, $$$a_1, a_2, \ldots, a_n$$$, of non-negative integers. For each $$$1 \leq i \leq n$$$, she has found a non-negative integer $$$x_i = max(0, a_1, \ldots, 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, \ldots, 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, \ldots, b_n$$$ and asks you to restore the values $$$a_1, a_2, \ldots, a_n$$$. Can you help her solve the problem?

Input

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

The next line contains $$$n$$$ integers, $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

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

Output

Print $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 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\}$$$.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/02/2022 05:51:26 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|