Background

$\text{brealid}$ thinks that the normal whack-a-mole game is too $\text{simple}$. So she designed a brand-new whack-a-mole game.

Problem Description

On a game window of length $l$, there is a mole sequence of length $t$ $(l \le t)$. Initially, the left end of the sequence is aligned with the left end of the window. Then the sequence moves one unit per second (that is, the leftmost mole leaves the window, and the rightmost mole enters the window), scrolling left until the player ends the game or the right end of the sequence coincides with the right end of the window (so the window always contains $l$ moles at any time).

In the first second after the game starts, the sequence does not move. It is not hard to see that the game will last at most $(t-l+1)$ seconds.

Each mole in sequence $T$ has its own height $h_i$. Each time, the player may choose to hit one mole. The player gains a coin reward equal to the mole’s height value $h_i$, and at the same time the height $h_i$ of mole $i$ decreases by one.

After research, $\text{brealid}$ adjusted the game speed so that while the mole sequence moves by one unit, the player can hit at most once (or choose not to hit).

Now $\text{brealid}$ tells you the window length $l$, the sequence length $t$, and the mole height sequence $T$ generated in a certain game. Our lovely $\text{brealid}$ wants to know the maximum coins she can get if she ends the game at any moment, that is, the maximum coins obtainable when stopping at second $1,2,\cdots (t-l+1)$, respectively.

Input Format

The first line contains two integers $l$ and $t$, representing the window length $l$ and the sequence length $t$.

The second line contains $t$ integers, representing the mole height sequence in a certain round.

Output Format

Output one line with $t-l+1$ integers $a_1,a_2,\cdots a_{t-l+1}$, where $a_i$ denotes the maximum number of coins that can be obtained if the game ends at second $i$.

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

3 5 6 7 12 16

Hint

Sample Explanation

Second 1: hit $2$, add $3$ to the answer.

Second 2: hit $2$, add $2$ to the answer.

Second 3: hit any one, add $1$ to the answer.

Second 4: hit any one again (a non-$0$ one), add $1$ to the answer.

Second 5: hit $9$, add $5$ to the answer.

Second 6: hit $9$, add $4$ to the answer.

Constraints

This problem uses bundled testdata. There are $4$ $\text{subtask}$ in total, and the final score is the sum of the scores of all $\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}$$

For $100\%$ of the testdata, $1\le l\le t\le 10^6$, $|h_i|\le 10^9$.

Translated by ChatGPT 5