# Prefix sum

Prefix sums are very handy when working with ranges in arrays. Itβs possible to optimize the programs many times by making use of the prefix sum of an array instead of calculating the sum every time.
Imagine a problem where we need to answer many queries (millions) βWhat will be the sum of elements of the array `a` from the beginning to ?β. So, a naive approach would be to calculate the sum `a[0] + a[1] + a[2] + ... + a[``]` every time. As an example, if we have an array and queries:
``````a = [8, 3, -2, 4, 10, -1, 0, 5]    # array
q = [3, 5, 2, 7]                   # queries``````
We can run a `for` loop to calculate the sum `a[0] + a[1] + a[2] + ... + a[``]` for every query, resulting in many repeated computations:
``````res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]``````
Notice how the first part of the computation is always the same. Before calculating `res2`, we already know the result of `a[0] + a[1] + a[2] + a[3]`, which was exactly `res1`. Before calculating `res4`, we already know the result for `a[0] + a[1] + a[2] + a[3] + a[4] + a[5]`. We can definitely optimize these calculations and respond to queries instantly instead of running a `for` loop every time.
To do that, we can store a new array `p` of prefix sums, where the elements of `p` will represent the sum of elements in the initial array `a` up to that index. If we do that, the answer to each query will be just accessing an element from the prefix sum:
``````p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]``````
Notice the pattern - to calculate the next element in the prefix array `p`, we repeat all the actions in the previous one and then add one more element from `a`. Having that, we can use the previous calculations to avoid adding the same numbers over and over:
``````p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]``````
This can be calculated with a single `for` loop in linear time instead of having multiple loops that do the same computation over and over. After computing the prefix sum array `p`, we will be able to answer all the queries instantly - as `p[i]` holds the information about the sum `a[0] + a[1] + a[2] + ... + a[i]`. So, for each query , the response will just be `p[``]`.
Can you calculate the prefix sum array now?

#### Input

The first line of the input contains a single integer `n` (1 β€ n β€ ). The second line of the input contains `n` space-separated integers representing the array `a` .

#### Output

The program should output the prefix sum array of `a`.

#### Examples

 Input Output 8 8 3 -2 4 10 -1 0 5 8 11 9 13 23 22 22 27
Β

#### Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 20 MB