Sanghoon 是 KOI 城市中经营商店的市民。Sanghoon 的商店里有 $N$ 件物品，第 $i$ 件物品的重量为 $A_i$。Sanghoon 得到情报：小偷 Kim Gibum 正在盯上他的商店，他想将损失最小化。

小偷 Kim Gibum 会从商店中偷走 $K$ 件物品。物品越重，越难偷走且越容易被警察抓到。因此，Kim Gibum 会使被偷物品的重量总和最小化。若商店里的物品数量少于 $K$，则 Kim Gibum 会偷走商店中的所有物品。

在小偷到来之前，Sanghoon 会把商店中的一些物品放进自己的背包并带走。之后，Kim Gibum 会按照上述方法，对 Sanghoon 没有带走的物品实施盗窃。Sanghoon 希望选择放入背包的物品，使得 Kim Gibum 最终偷走的物品重量总和尽可能大。

Sanghoon 的背包有重量容量限制。给定最大容量 $C$，请对所有 $x = 1, 2, \ldots, C$ 回答下面的问题：

在 Sanghoon 放入背包的物品总重量不超过 $x$ 的条件下，Kim Gibum 可能偷走的物品重量总和的最大值是多少？

限制

所有给定数字均为整数。

• $1 \le K \le N \le 5000$
• $1 \le C \le 1\,000\,000$
• 对所有 $i \ (1 \le i \le N)$，$1 \le A_i \le 1\,000\,000$

子任务

1. (13 分) $N \le 10$，$A_i \le 10\,000$，$C \le 10\,000$
2. (17 分) $N \le 80$，$A_i \le 10\,000$，$C \le 10\,000$
3. (23 分) $A_i \le 10\,000$，$C \le 10\,000$
4. (16 分) $K = 1$
5. (31 分) 无额外限制

输入格式

第一行包含 $N$、$K$、$C$，以空格分隔。
第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，以空格分隔。

输出格式

输出 $C$ 行。
第 $i$ 行输出当 $x = i$ 时，Kim Gibum 偷走的物品重量总和的最大可能值。

样例数据

样例 1

输入

5 1 6
1 2 3 4 5

输出

2
2
3
3
3
4

样例 2

输入

5 2 5
2 3 5 7 11

输出

5
8
8
8
12

样例 3

输入

3 2 3
1 1 7

输出

8
8
8