题目背景

$\text{brealid}$ 觉得普通的打地鼠游戏太过于 $\text{simple}$ 了。所以，她设计了一款全新的打地鼠游戏。

题目描述

在长度为 $l$ 的游戏窗口上，有一个长为 $t$ 的地鼠序列 $(l \le t)$，初始序列左端与窗口左端对齐，接下来序列每秒移动一个单位长度，（即最左端的地鼠离开窗口，最右端的地鼠进入窗口），向左滚动直至玩家结束游戏或者序列最右端与窗口最右端重合（即任何时刻窗口内均应有 $l$ 只地鼠）。

游戏开始的第一秒序列不会移动，不难发现游戏最多会进行 $(t-l+1)$ 秒。

序列 $T$ 中的每一只地鼠都有自己的高度 $h_i$，玩家每次可以选择击打一只地鼠，玩家可以获得与地鼠高度 $h_i$ 数值相同的金币奖励，同时地鼠 $i$ 的高度 $h_i$ 会减一。

经过调研，$\text{brealid}$ 控制了游戏运行速度，使得玩家在地鼠序列移动一个单位长度的同时最多只能打击一次（也可以不打）。

现在 $\text{brealid}$ 告诉了你某一次游戏的窗口长度 $l$、序列长度 $t$ 以及某一局游戏中生成的地鼠高度序列 $T$。我们可爱的 $\text{brealid}$ 想要知道，她在任意时刻结束游戏所能得到的最多金币，即在第 $1,2,\cdots (t-l+1)$ 秒时停止游戏分别可以获得的最多金币。

输入格式

第一行两个整数 $l$，$t$，表示窗口长度 $l$ 和序列长度 $t$。

第二行 $t$ 个整数，表示某一局中的地鼠高度序列。

输出格式

一行 $t-l+1$ 个整数 $a_1,a_2,\cdots a_{t-l+1}$，$a_i$ 表示第 $i$ 秒时结束游戏可以获得的最多的金币数。

5 10
1 3 1 1 1 1 1 1 5 1

3 5 6 7 12 16

提示

样例解释

第一秒：锤 $2$，答案加 $3$。

第二秒：锤 $2$，答案加 $2$。

第三秒：随便锤一个，答案加 $1$。

第四秒：再随便锤一个（非 $0$ 的），答案加 $1$。

第五秒：锤 $9$，答案加 $5$。

第六秒：锤 $9$，答案加 $4$。

数据范围

本题采用捆绑测试，共有 $4$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & l\le t\le \cr\hline 1 & 10 & 10 \cr\hline 2 & 20 & 500 \cr\hline 3 & 30 & 5000 \cr\hline 4 & 40 & 10^6 \cr\hline \end{array} $$

对于 $100\%$ 的数据，$1\le l\le t\le 10^6$，$|h_i|\le 10^9$。