Gambling Assistant

Task

Giorgio has been recently introduced to a gambling club, where he is accurately losing all of his money. Tired of losing so much, he chooses one of the simplest games played there and tries his best to become good at it. This game consists in a series of $N$ rounds, in which every player draws a card from a deck (represented by a number from $1$ to $13$). The hand size is limited to $K$ cards, so that whenever a player exceeds this limit he has to immediately discard one card from his hand. During the game several bets take place, that are won by the player with the highest grand total (sum of the values - from $1$ to $13$ - of each card) in his hand.

To improve his performance in the game, Giorgio is reviewing some videos of famous plays of this game. In this videos he is able to see which card $C_i$ is drawn at each round, but he is not able to easily keep track of the grand total as it varies during the game. Help Giorgio in determining the highest grand total $G_i$ that a player can have at each round, given the list of cards $C_i$ drawn!

Input data

The first line contains the two integers $N$ and $K$. The second line contains $N$ integers $C_i$.

Output data

You need to write a single line with $N$ integers $G_i$, the highest grand total possible when drawing the given cards.

Constraints and clarifications

• $1 \le K \le N \le 1\,000\,000$.
• $1 \le C_i \le 13$ for each $i=0\ldots N-1$.
• The constraints shown in PDF are wrong.

Example 1

stdin

4 2
10 4 10 12

stdout

10 14 20 22

Explanation

In the first sample case, the hands kept by the player (in order) are: $[10], [4, 10], [10, 10], [10, 12]$.

Example 2

stdin

8 5
4 13 10 2 7 1 13 7

stdout

4 17 27 29 36 36 47 50

Explanation

In the second sample case, the hands kept by the player (in order) are: $[4]$, $[4, 13]$, $[4, 10, 13]$, $[2, 4, 10, 13]$, $[2, 4, 7, 10, 13]$, $[2, 4, 7, 10, 13]$, $[4, 7, 10, 13, 13]$, $[7, 7, 10, 13, 13]$.