CF1253C.Sweets Eating

Tsumugi brought $n$ delicious sweets to the Light Music Club. They are numbered from $1$ to $n$, where the $i$-th sweet has a sugar concentration described by an integer $a_i$.

Yui loves sweets, but she can eat at most $m$ sweets each day for health reasons.

Days are $1$-indexed (numbered $1, 2, 3, \ldots$). Eating the sweet $i$ at the $d$-th day will cause a sugar penalty of $(d \cdot a_i)$, as sweets become more sugary with time. A sweet can be eaten at most once.

The total sugar penalty will be the sum of the individual penalties of each sweet eaten.

Suppose that Yui chooses exactly $k$ sweets, and eats them in any order she wants. What is the minimum total sugar penalty she can get?

Since Yui is an undecided girl, she wants you to answer this question for every value of $k$ between $1$ and $n$.

Tsumugi 给轻音部带来了 $n$ 颗美味的糖果。这些糖果编号为 $1$ 到 $n$，其中第 $i$ 颗糖果的糖分浓度由整数 $a_i$ 描述。

Yui 喜欢吃糖果，但出于健康原因，她每天最多只能吃 $m$ 颗糖果。

天数从 $1$ 开始编号（即第 $1$ 天、第 $2$ 天、第 $3$ 天……）。若在第 $d$ 天吃掉第 $i$ 颗糖果，则会产生 $(d \cdot a_i)$ 的糖分惩罚，因为随着时间推移，糖果会变得越来越甜。每颗糖果至多被吃一次。

总糖分惩罚等于所有被吃掉的糖果各自惩罚值之和。

假设 Yui 恰好选择 $k$ 颗糖果，并以任意她喜欢的顺序吃掉它们。她所能获得的最小总糖分惩罚是多少？

由于 Yui 是个优柔寡断的女孩，她希望你对每个 $k = 1, 2, \ldots, n$ 分别回答这个问题。

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 200\ 000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 200\ 000$).

第一行包含两个整数 $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$）。

You have to output $n$ integers $x_1, x_2, \ldots, x_n$ on a single line, separed by spaces, where $x_k$ is the minimum total sugar penalty Yui can get if she eats exactly $k$ sweets.

你需要在一行中输出 $n$ 个整数 $x_1, x_2, \ldots, x_n$，以空格分隔，其中 $x_k$ 表示若由依恰好吃掉 $k$ 颗糖果时所能得到的最小总糖分惩罚值。

Let's analyze the answer for $k = 5$ in the first example. Here is one of the possible ways to eat $5$ sweets that minimize total sugar penalty:

• Day $1$: sweets $1$ and $4$
• Day $2$: sweets $5$ and $3$
• Day $3$ : sweet $6$

Total penalty is $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$. We can prove that it's the minimum total sugar penalty Yui can achieve if she eats $5$ sweets, hence $x_5 = 30$.

我们来分析第一个示例中 $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$ 颗糖果，则该总糖分惩罚 $30$ 是她所能达到的最小值，因此 $x_5 = 30$。