問題文

なぎさちゃんの別荘は N 個の部屋と N-1 本の通路からなり、各部屋には 1 から N の、各通路には 1 から N-1 の番号が割り振られています。i 番目の通路は部屋 i と 部屋 i+1 を双方向に繋いでおり、整数 C_i が書かれています。

いろはちゃんは今朝、この内のある部屋で目が覚めました。忍者であるいろはちゃんは、忍術を使って抜け出すことにしました。いろはちゃんの気分は整数で表され、これが高いほど忍術が成功しやすいです。気分の値は初め 0 であり、通路 i を通ると気分に C_i が加算されますが、仕掛けが作動してその通路が通れなくなります。
スタートする部屋を r として、通路を 0 回以上通って好きな部屋で立ち止まるときの、気分の最大値を X_r とします。
全ての部屋 i に対して X_i を求めて下さい。

入力

入力は、以下の形式で標準入力より与えられます。

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

出力

全部で N 行出力してください。
i 行目には X_i 、つまり部屋 i から始めたときの気分の最大値を出力してください。

入力例 1

5
70
10
50
20

出力例 1

150
80
80
130
150

この入力例において、別荘の図は以下のようになっています。

例えば部屋 3 から出発した場合、3 → 2 → 1 というルートを通り部屋 1 で立ち止まるとき、気分が 10 + 70 = 80 が得られます。
また、これより良い気分を得る方法はありません。

入力例 2

8
70
10
-2000
10000
-2000
50
20

出力例 2

8080
8010
8000
10000
10000
8000
8050
8070

この入力は、小課題 1, 2 の制約を満たしません。

入力例 3

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

出力例 3

0
0
0
0
0
0
0