C. Поедание конфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Tsumugi купила $$$n$$$ вкусных конфет в Light Music Club. Они пронумерованы целыми числами от $$$1$$$ до $$$n$$$, у $$$i$$$-й конфеты концентрация сахара описана целым числом $$$a_i$$$.

Yui любит конфеты, но она может есть не более $$$m$$$ конфет каждый день, из соображений здоровья.

Дни нумеруются в $$$1$$$-индексации (пронумерованы $$$1, 2, 3, \ldots$$$). Съесть конфету $$$i$$$ в $$$d$$$-й день будет стоить $$$(d \cdot a_i)$$$ сахарного штрафа, так как со временем конфеты становятся более сладкими. Каждая конфета может быть съедена не более одного раза.

Итоговый сахарный штраф равен сумме сахарных штрафов всех съеденных конфет.

Предположим, что Yui выбирает ровно $$$k$$$ конфет, и ест их в любом порядке, в каком захочет. Какой минимальный сахарный штраф она может получить?

Так как Yui нерешительная девушка, она просит ответить вас на этот вопрос для всех $$$k$$$ от $$$1$$$ до $$$n$$$.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 200\ 000$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\ 000$$$).

Выходные данные

Вы должны вывести $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ в отдельной строке, разделяя пробелами, где $$$x_k$$$ это минимальный сахарный штраф который Yui может получить, съев ровно $$$k$$$ конфет.

Примеры
Входные данные
9 2
6 19 3 4 4 2 6 7 8
Выходные данные
2 5 11 18 30 43 62 83 121
Входные данные
1 1
7
Выходные данные
7
Примечание

Проанилизируем ответ для $$$k = 5$$$ первого примера. Вот один из возможных способов съесть $$$5$$$ конфет, чтобы минимизировать суммарный сахарный штраф:

  • День $$$1$$$: конфеты $$$1$$$ и $$$4$$$
  • День $$$2$$$: конфеты $$$5$$$ и $$$3$$$
  • День $$$3$$$ : конфета $$$6$$$

Итоговый штраф равен $$$1 \cdot a_1 + 1 \cdot a_4 + 2 \cdot a_5 + 2 \cdot a_3 + 3 \cdot a_6 = 6 + 4 + 8 + 6 + 6 = 30$$$. Мы можем доказать, что это минимальный возможный сахарный штраф, который Yui может получить если она съест $$$5$$$ конфет, таким образом $$$x_5 = 30$$$.