题目描述

商户是在 KOI 市经营商店的一位市民。商户的店里有 $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$ 时，小偷金基范偷走的商品总重量的最大值。

输入输出样例 #1

输入 #1

5 1 6
1 2 3 4 5

输出 #1

2
2
3
3
3
4

输入输出样例 #2

输入 #2

5 2 5
2 3 5 7 11

输出 #2

5
8
8
8
12

输入输出样例 #3

输入 #3

3 2 3
1 1 7

输出 #3

8
8
8

说明/提示

限制条件

• 所有给定的数都是整数。
• $1 \le K \le N \le 5\,000$
• $1 \le C \le 1\,000\,000$
• 对于所有 $i$ ($1 \le i \le N$)，满足 $1 \le A_i \le 1\,000\,000$

子任务

1. 30%：$N \le 10, A_i \le 10\,000, C \le 10\,000$
2. 30%：$N \le 80, A_i \le 10\,000, C \le 10\,000$
3. 20%：$A_i \le 10\,000, C \le 10\,000$
4. 10%：$K = 1$（cin会超时）
5. 10%：无额外限制条件。