Лена учится играть на пианино. У нее есть n
композиций, упорядоченных по возрастанию сложности. Для каждой композиции Лена знает время, которое ей потребуется для ее исполнения. Перед тем, как начать учиться, она выбирает целое число
L
от 1 до
n
включительно и строит свою программу обучения следующим образом: в первый день она играет композиции
1
,
2
,
.
.
.
,
L
, во второй день композиции
2
,
3
,
.
.
.
,
L
+
1
и так далее. В день, когда Лена играет последнюю композицию, обучение заканчивается (действительно, она же успешно сыграла самую сложную композицию).

Лена заметила, что от выбора
L
время, которое она проведет за исполнением композиций, меняется. Ей стало интересно, сколько времени она проведет за исполнением композиций, если выберет
L
=
1
,
2
,
.
.
.
,
n
.

Требуется написать программу, которая для каждого
L
=
1
,
2
,
.
.
.
,
n
подсчитывает суммарное время, которое Лена потратит на исполнение композиций при заданном
L
.

Входные данные
В первой строке записано число
n
(
1
≤
n
≤
3
⋅
10
5
)
– количество композиций. В следующей строке через пробел записаны
n
чисел
a
1
,
a
2
,
.
.
.
,
a
n
(
1
≤
a
i
≤
10
7
)
, где
a
i
– время исполнения
i
-й композиции

Выходные данные
Выведите
n
чисел через пробел – суммарное время для
L
=
1
,
2
,
.
.
.
,
n
соответственно.

Система оценки
Решения, работающие правильно при
n
≤
5
, будут набирать не менее

Решения, работающие правильно при
n
≤
300
, будут набирать не менее

Решения, работающие правильно при
n
≤
10
000
, будут набирать не менее

Примеры
входные данные
4
1 3 2 4
выходные данные
10 15 15 10
входные данные
5
5 1 3 5 4
выходные данные
18 27 30 27 18
Примечание
Обращаем ваше внимание на то, что ответ в данной задаче может быть достаточно большим, поэтому рекомендуем использовать 64-битный тип данных. В C++ для этого предусмотрен тип long long, в Pascal – int64.

Так же, давайте разберем первый пример из условия:

При
L
=
1
В первый день Лена потратит 1 минуту

Во второй – 3 минуты

В третий – 2 минуты

И в четвертый – 4 минуты

Итого 1+3+2+4=10 минут

При
L
=
2
В первый день Лена потратит 1+3=4 минуты

Во второй – 3+2=5 минут

В третий – 2+4=6 минут и закончит обучение, так как сыграет последнюю композицию

Итого 4+5+6=15 минут

При
L
=
3
В первый день Лена потратит 1+3+2=6 минут

Во второй – 3+2+4=9 минут

Итого 6+9=15 минут

При
L
=
4
В первый и единственный день Лена потратит 1+2+3+4=10 минут