Problem Description

You are enjoying "Snuke's Upbringing". You want your beloved Snuke to become as smart as possible, so you decided to train his intelligence.

In "Snuke's Upbringing", you can consume "Stamina" to train Snuke's intelligence. For each unit of Stamina consumed, Snuke's intelligence increases by 1.

Stamina recovers by 1 unit per unit time, up to a maximum of $X$. If the Stamina is already at the upper limit $X$, it does not recover over time. Also, Stamina cannot be reduced to less than 0. Initially, at time $0$, the Stamina is full, i.e., it is $X$.

Of course, it is most efficient to consume Stamina as soon as it recovers, but unfortunately, you have matters to attend to in the real world and cannot play "Snuke's Upbringing" all the time (real life is often inflexible).

Still, you managed to find $N$ possible times to launch the game. The $i$-th candidate is at time $T_i$. Due to your busy schedule, once you launch the game, you must quickly consume all available Stamina and exit the game. That is, if there is $s$ Stamina left at time $T_i$, you can consume any non-negative integer amount of Stamina up to $s$, increasing Snuke's intelligence by the amount consumed, but you cannot do any other operations.

You are unsure how busy you will be in the future, so for each $K=1,2,...,N$, you decided to calculate the maximum intelligence Snuke can achieve if you launch the game at most $K$ times out of the $N$ candidate times. Please find all $N$ values.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ T_1 $ : $ T_N $

Output Format

For each $K=1,2,...,N$, output the maximum final intelligence of Snuke.

Sample Input and Output

Sample Input #1

3 3
2
4
6

Sample Output #1

3
6
7

Sample Input #2

5 4
4
5
7
8
11

Sample Output #2

4
8
11
11
11

Sample Input #3

7 5
2
4
10
12
13
17
20

Sample Output #3

5
10
15
18
20
22
22

Notes/Hints

Constraints

• $1 \leq N \leq 5000$
• $1 \leq X \leq 10^9$
• $1 \leq T_i \leq 10^9 (1 \leq i \leq N)$
• $T_i < T_{i+1} (1 \leq i \leq N-1)$
• All inputs are integers

Sample Explanation 1

For $K=1$, you should consume 3 Stamina at time 4. For $K=2$, consume 3 Stamina at time 2 and 3 Stamina at time 6. For $K=3$, consume 3 Stamina at time 2, 2 Stamina at time 4, and 2 Stamina at time 6.

见题面 Input 部分

见题面 Output 部分