Problem Description

Nagisa's villa consists of $ N $ rooms and $ N-1 $ corridors, with each room numbered from $ 1 $ to $ N $ and each corridor numbered from $ 1 $ to $ N-1 $. The $ i $-th corridor connects room $ i $ and room $ i+1 $ bidirectionally, and has an integer $ C_i $ written on it.

Iroha woke up in one of these rooms this morning. Being a ninja, Iroha decided to use ninjutsu to escape. Iroha's mood is represented by an integer, and the higher it is, the more likely the ninjutsu will succeed. The mood value initially starts at $ 0 $. When passing through corridor $ i $, the mood value is increased by $ C_i $, but the trap activates and the corridor becomes impassable.

Let the starting room be $ r $. The maximum mood value $ X_r $ when stopping at any room after passing through the corridors $ 0 $ or more times is defined.

For every room $ i $, find $ X_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ C_1 $ $ C_2 $ $ C_3 $ ... $ C_{N-1} $

Output Format

Output a total of $ N $ lines.
The $ i $-th line should contain $ X_i $, the maximum mood value when starting from room $ i $.

Sample Input and Output

Sample Input #1

5
70
10
50
20

Sample Output #1

150
80
80
130
150

Sample Input #2

8
70
10
-2000
10000
-2000
50
20

Sample Output #2

8080
8010
8000
10000
10000
8000
8050
8070

Sample Input #3

7
-45
-45
-45
-45
-45
-45

Sample Output #3

0
0
0
0
0
0
0

Notes/Hints

Constraints

• $2 \leq N \leq 100000$
• $-10^9 \leq C_i \leq 10^9$

Subtasks

Subtask $ 1 $ [$ 15 $ points]

• $N \leq 1000$
• All $ C_i $ are non-negative.

Subtask $ 2 $ [$ 30 $ points]

• All $ C_i $ are non-negative.

Subtask $ 3 $ [$ 55 $ points]

• No additional constraints.

Sample Explanation 1

In this input example, the layout of the villa is as follows: For example, if starting from room $ 3 $, taking the route $3 \rightarrow 2 \rightarrow 1$ and stopping at room $ 1 $, the mood value obtained is $ 10 + 70 = 80 $. There is no better way to increase the mood value.

Sample Explanation 2

This input does not satisfy the constraints of Subtask $ 1 $ or $ 2 $.

见题面 Input 部分

见题面 Output 部分