Given an array ~A~ of ~N \ (1 \le N \le 10^4)~ elements ~a_1, a_2,..., a_N \ (1 \le a_i \le 3)~, perform the following operation twice:

• for all ~i \ (1 < i \le N)~ set ~a_i = a_{i-1} + a_i~

and output the final array.

Input Specification

The first line of input will contain ~N~.

The next line will contain ~N~ space-separated integers ~a_i~.

Output Specification

Output each element of the array on one line, space-separated, after performing the above operation twice.

Sample Input

5
1 2 1 3 2

Sample Output

1 4 8 15 24

Explanation

Performing the operation once, the array is now:

~[1, 3, 4, 7, 9]~

Performing the operation again, the array is now:

~[1, 4, 8, 15, 24]~