CF1253C Sweets Eating

Tsumugi 给轻音部带来了 $n$ 份美味的甜点。它们编号为 $1$ 到 $n$，其中第 $i$ 份甜点的含糖量为整数 $a_i$。 Yui 很喜欢甜点，但出于健康原因，她每天最多只能吃 $m$ 份甜点。 天数从 $1$ 开始编号（即 $1, 2, 3, \ldots$）。在第 $d$ 天吃第 $i$ 份甜点会产生一个糖分惩罚值 $(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$ 份甜点时能获得的最小总糖分惩罚值。

我们来分析第一个样例中 $k=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$。 由 ChatGPT 4.1 翻译