Problem Statement

You have a row of $N$ cells. The $i$-th cell from the left contains an integer $A_i$.

You also have $\lfloor \frac{N}{K} \rfloor$ tiles, each of which covers $K$ consecutive cells.

For each $i = 1, \ldots, \lfloor \frac{N}{K} \rfloor$, solve the following problem:

• When placing exactly $i$ tiles without overlap, find the maximum possible sum of the numbers in the covered cells.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq \min(5,N)$
• $-10^9 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the answers for $i = 1, \ldots, \lfloor \frac{N}{K} \rfloor$ separated by spaces in one line.