紬给轻音乐社带来了$$$n$$$美味的糖果。它们的编号从 $$$1$$$ 到 $$$n$$$,其中第 $$$i$$$ 个糖果的糖浓度由整数 $$$a_i$$$ 描述。
Yui喜欢甜食,但出于健康原因,她每天最多只能吃$$$m$$$甜食。
天按 $$$1$$$ 索引(编号为 $$$1, 2, 3, \ldots$$$)。在第 $$$d$$$ 天吃甜食 $$$i$$$ 会导致糖分损失 $$$(d \cdot a_i)$$$,因为随着时间的推移,甜食变得越来越含糖。一颗甜食最多可以吃一次。
总糖罚分将是所吃的每种甜食的单独罚分之和。
假设 Yui 恰好选择了 $$$k$$$ 糖果,并按照她想要的任何顺序吃掉它们。她能得到的最低总糖罚分是多少?
由于 Yui 是一个犹豫不决的女孩,她希望您针对 $$$1$$$ 和 $$$n$$$ 之间的每个 $$$k$$$ 值回答这个问题。
输入
第一行包含两个整数 $$$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$$$ 糖果后可以获得的最小总糖罚分。
示例
输入 #1
9 2 6 19 3 4 4 2 6 7 8
输出 #1
2 5 11 18 30 43 62 83 121
输入 #2
1 1 7
输出 #2
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$$$。