AT_abc383_g.[ABC383G] Bar Cover

你有一排 $N$ 个格子，第 $i$ 个格子（从左到右）包含一个整数 $A _ i$。

你还有 $\lfloor \frac{N} {K} \rfloor$ 块瓷砖，每块瓷砖可以覆盖连续的 $K$ 个格子。

对于每一个 $i = 1, \ldots, \lfloor \frac{N} {K} \rfloor$，解决如下问题：

• 恰好放置 $i$ 块瓷砖且不重叠时，求所覆盖格子中数字之和的最大值。

输入以如下格式从标准输入中给出：

$N$ $K$
$A_1$ $\ldots$ $A_N$

将 $i = 1, \ldots, \lfloor \frac{N} {K} \rfloor$ 的答案依次用空格分隔输出在一行。

「数据范围」

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq \min(5, N)$
• $-10^9 \leq A_i \leq 10^9$
• 所有输入值均为整数。

「样例 1 解释」

对于 $i=1$，如果用一个瓷砖覆盖第 2 和第 3 个格子，被覆盖格子的数字之和为 $7$。

对于 $i=2$，如果用一个瓷砖覆盖第 2 和第 3 个格子，再用另一个瓷砖覆盖第 4 和第 5 个格子，被覆盖格子的数字之和为 $12$。