题目描述

商店里有 $n$ 件商品，其中第 $i$ 件商品的重量为 $a_i$。店主收到了情报，得知小偷正觊觎自己的店铺，于是他准备采取措施，将损失降到最低。

小偷计划从店里偷走 $k$ 件商品。但如果商品太重，不仅难以偷窃，被警察抓住的可能性也会变高。因此，小偷会最小化他所偷商品的总重量。

• 不过，如果店里的商品总数不足 $k$ 件，小偷会偷走店里所有的商品。

在小偷到达店铺之前，店主会把店里的一些商品装进一个包里带走。之后，小偷会对店主没有带走的那些商品，以上述方式实施盗窃。

店主希望通过合理地往包里装商品，来最大化小偷最终偷走的商品总重量。

店主的包能承受的重量是有限的。当给定一个最大承重 $c$ 时，请对所有的 $x = 1, 2, \ldots, c$ 回答以下问题：

在店主能放入包中的商品总重量不超过 $x$ 的条件下，小偷偷走的商品总重量的最大值是多少？

输入格式

第一行给定 $n, k, c$，由空格分隔。

第二行给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$，由空格分隔。

输出格式

输出 $c$ 行。第 $i$ 行输出当 $x = i$ 时，小偷偷走的商品总重量的最大值。

5 1 6
1 2 3 4 5

2
2
3
3
3
4

5 2 5
2 3 5 7 11

5
8
8
8
12

3 2 3
1 1 7

8
8
8

提示

样例 1 解释

• 当 $x=1$，店主带走商品 $a_1$，小偷拿走 $a_2$。
• 当 $x=2$，店主带走商品 $a_1$，小偷拿走 $a_2$。
• 当 $x=3$，店主带走商品 $a_1,a_2$，小偷拿走 $a_3$。
• 当 $x=4$，店主带走商品 $a_1,a_2$，小偷拿走 $a_3$。
• 当 $x=5$，店主带走商品 $a_1,a_2$，小偷拿走 $a_3$。
• 当 $x=6$，店主带走商品 $a_1,a_2,a_3$，小偷拿走 $a_4$。

因此输出分别是 2 2 3 3 3 4。

样例 3 解释

由于小偷要偷两件物品，因此不论 $x$ 是多少，店主都只带走商品 $a_1$，小偷不得不拿走 $a_2+a_3=8$ 这样可以最大化小偷偷走的总重量。

数据范围

对于 $100\%$ 的数据满足：$1 \le k \le n \le 5\,000$，$1 \le c \le 1\,000\,000$，$1 \le a_i \le 1\,000\,000$。