Alicia 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\}$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
ls = list(map(int, input().split()))

msf = 0
res = []
for e in ls:
    v = msf + e
    msf = max(msf, v)
    res.append(v)

for e in res:
    print(e, end=' ')


a = int(input())
b = 0
c = list(map(int, input().split()))
for i in c:
    if i > 0:
        b += i
        print(b, end=' ')
    elif i < 0:
        print(b + i, end=' ')
    else:
        print(b, end=' ')

#!/usr/bin/env python
#-*- coding:utf-8 -*-

# Code by H~$~C

from sys import stdin
input = stdin.readline
import math

n = int(input())
arr = list(map(int, input().split()))
mx = 0
for i in range(n):
  print(arr[i] + mx, end = ' ')
  mx = max(mx, arr[i] + mx)
print()

n = int(input())
b = list(map(int, input().split()))
a = []
max_so_far = 0
for i in range(n):
    a.append(b[i]+max_so_far)
    max_so_far = max(max_so_far, a[-1])
print(*a)