Sanghoon is a citizen who runs a shop in KOI City. Sanghoon’s shop has $N$ items, and the weight of the $i$-th item is $A_i$. Sanghoon has received intelligence that a thief, Kim Gibum, is targeting his shop, and he wants to minimize the damage.

The thief Kim Gibum will steal $K$ items from the shop. If items are heavy, they are difficult to steal and increase the likelihood of being caught by the police. Therefore, Kim Gibum minimizes the sum of the weights of the stolen items. If the number of items in the shop is less than $K$, Kim Gibum steals all items in the shop.

Before the thief arrives, Sanghoon will put some of the shop’s items into his bag and carry them away. After that, Kim Gibum commits the crime according to the method described above on the items that Sanghoon did not take. Sanghoon wants to choose items to put into his bag so as to maximize the total weight of the items that Kim Gibum steals.

Sanghoon’s bag has a limited weight capacity. Given the maximum capacity $C$, answer the following question for all $x = 1, 2, \ldots, C$:

Under the condition that the total weight of the items Sanghoon puts into his bag is at most $x$, what is the maximum possible total weight of the items that Kim Gibum steals?

Constraints

All given numbers are integers.

• $1 \le K \le N \le 5000$
• $1 \le C \le 1\,000\,000$
• For all $i \ (1 \le i \le N)$, $1 \le A_i \le 1\,000\,000$

Scoring

1. (13 points) $N \le 10$, $A_i \le 10\,000$, $C \le 10\,000$
2. (17 points) $N \le 80$, $A_i \le 10\,000$, $C \le 10\,000$
3. (23 points) $A_i \le 10\,000$, $C \le 10\,000$
4. (16 points) $K = 1$
5. (31 points) No additional constraints

Input Format

The first line contains $N$, $K$, and $C$, separated by spaces.
The second line contains $N$ integers $A_1, A_2, \ldots, A_N$, separated by spaces.

Output Format

Output $C$ lines.
On the $i$-th line, output the maximum possible total weight of the items that Kim Gibum steals when $x = i$.

Example

Example 1

Input

5 1 6
1 2 3 4 5

Output

2
2
3
3
3
4

Example 2

Input

5 2 5
2 3 5 7 11

Output

5
8
8
8
12

Example 3

Input

3 2 3
1 1 7

Output

8
8
8