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\}.
The above is tricky. Write me a correct solution in PYTHON3.
 ... What is a Python program 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 program 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, .

import sys
#from collections import defaultdict
#from collections import Counter
#import math
#from fractions import Fraction
#import heapq
#from bisect import bisect_left

def main():

    def GCD(x, y):
        while (y):
            x, y = y, x % y
        return x
    def lcm(a,b):
        return (a*b)//GCD(a,b)
    # Modified merge for inversion
    def merge(a,start,mid,end,d):
        p=start
        q=mid+1
        arr=[0]*(end-start+1)
        k=0
        coun=0
        for i in range(start,end+1):
            if p > mid:
                arr[k]=a[q]
                q+=1
                k+=1
            elif q > end:
                arr[k]=a[p]
                d[a[p]] += coun
                k+=1
                p+=1
            elif a[p] < a[q]:
                arr[k]=a[p]
                d[a[p]]+=coun
                k+=1
                p+=1
            else:
                arr[k]=a[q]
                k+=1
                q+=1
                coun+=1

        for i in range(k):
            a[start]=arr[i]
            start+=1
    def mergesort(a, start, end,d):
        if start<end:
            mid=(start+end)//2
            mergesort(a,start,mid,d)
            mergesort(a,mid+1,end,d)
            merge(a,start,mid,end,d)
    # inversion return dic for every index inversion count
    def inversion(l):
        d={}
        for i in l:
            d[i]=0
        mergesort(l,0,len(l)-1,d)
        return d
    def binary_search_lower(A,low,high,k):
        if high-low!=1:
            mid=(low+high)//2
            x = A[mid]
            if x>=k:
                return binary_search_lower(A,low,mid,k)
            else:
                return binary_search_lower(A,mid,high,k)
        if A[low]>=k:
            return low
        else:
            return high
    # Function to find power
    def binary_expo(x,n):
        if n==0:
            return 1
        elif n%2==0:
            return binary_expo(x*x,n//2)
        else:
            return x*binary_expo(x*x,(n-1)//2)
    # Function to find power with...