Mimi decides to play a game with the following rules:

A ~k~-subarray is a subarray of length ~k~.

The ~k~-uteness of an array ~A~ is defined as the sum of all ~k~-subarrays of ~A~.

The winner is the person who can output the ~k~-uteness of ~A~ for ~k = 1, 2, \dots, N~, where ~N~ is the number of elements in ~A~. Can you beat Mimi?

Constraints

For all subtasks:

~1 \le A_i \le 10^9~

Subtask 1 [10%]

~1 \le N \le 500~

Subtask 2 [10%]

~1 \le N \le 2\,000~

Subtask 3 [80%]

~1 \le N \le 200\,000~

Input Specification

The first line of input will contain a single integer, ~N~.
The next line of input will contain ~N~ space separated integers, ~A_1, A_2, \dots, A_N~.

Output Specification

~N~ lines, with the ~k^\text{th}~ line being the ~k~-uteness of the array.

Sample Input

5
1 1 1 1 1

Sample Output

5
8
9
8
5