Given an array of integers call nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Output the running sum of nums.

Input

The first line contains an integer n (~0~ < n < ~10^{6}~) which is the length of the array nums

The second line contains n integers which are the elements in the array nums

Output

Only one line contains the elements in the array runningSum. All elements are separated by a space.

Example

Input

4
1 2 3 4

Output

1 3 6 10