题目描述

给定一个整数序列 $A = (A_1, \\dots, A_N)$，长度为 $N$，以及整数 $M$ 和 $K$。
对于每个 $i = 1, \\dots, N - M + 1$，解决下面的独立问题。

在升序排序的 $M$ 个整数 $A_i, A_{i + 1}, \\dots, A_{i + M - 1}$ 的列表中，找到前 $K$ 个值的和。

约束条件

• $1 \\leq K \\leq M \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i \\leq 10^9$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $A_1$ $A_2$ $\\ldots$ $A_N$

输出

设 $\\mathrm{answer}_k$ 是第 $k$ 个问题的答案，按以下格式输出：

$\\mathrm{answer}_1$ $\\mathrm{answer}_2$ $\\ldots$ $\\mathrm{answer}_{N-M+1}$

示例输入 1

6 4 3
3 1 4 1 5 9

示例输出 1

5 6 10

• 对于 $i = 1$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 升序排序得到 $1, 1, 3, 4$，前三个值的和为 $5$。
• 对于 $i = 2$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 升序排序得到 $1, 1, 4, 5$，前三个值的和为 $6$。
• 对于 $i = 3$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 升序排序得到 $1, 4, 5, 9$，前三个值的和为 $10$。

示例输入 2

10 6 3
12 2 17 11 19 8 4 3 6 20

示例输出 2

21 14 15 13 13