human
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\}.

=====
Write me a Python code to 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,?
assistant
#Here is Python code to 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, .

mod=10**9+7
#import resource
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#import threading
#threading.stack_size(2**27)
import sys
#sys.setrecursionlimit(10**6)
#fact=[1]
#for i in range(1,100001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*100001
#ifact[100000]=pow(fact[100000],mod-2,mod)
#for i in range(100000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
from bisect import bisect_right as br             #c++ upperbound
import itertools
import collections
import math
import heapq
#from random import randint as rn
#from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r):                        #for using this uncomment the lines calculating fact and ifact
    t=((fact[n])*((ifact[r]*ifact[n-r])%mod))%mod
    return t
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input().strip()
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x
"""*******************************************************"""
def main():
    n=int(sin())
    b=ain()
    m=0
    for i in range(n):
        t=b[i]+m
        m=max(t,m)
        print t,
    print
####### Python 2 and 3 footer by Pajenegod and c1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while...