問題文

あなたは、「すぬけそだて」を楽しんでいます。愛しのすぬけ君をできるだけ賢いねこにしたいあなたは、すぬけ君の知力トレーニングをすることにしました。

「すぬけそだて」では、あなたは「スタミナ」を消費してすぬけ君の知力をトレーニングすることができます。スタミナを 1 消費するごとに、すぬけ君の知力は 1 だけ上がります。

スタミナは、1 単位時間に 1 だけ、最大で X まで回復します。スタミナが上限 X に達している場合、時間経過でスタミナが回復することはありません。 また、スタミナを 0 未満にすることはできません。初期状態、すなわち時刻 O において、スタミナは満タンに、すなわち X だけ溜まっています。

もちろん、スタミナが溜まったらすぐに消費するのが最も効率的なのですが、残念なことにあなたには現実世界での用事があり、 四六時中「すぬけそだて」を遊んでいるというわけにはいきません(現実の生活というのは、往々にして融通の利かないものです)。

それでも、あなたは多忙な生活の合間を縫って、「すぬけそだて」を起動できる時間の候補を N 個ひねり出しました。i 個目の候補は時刻 T_i です。 あなたは多忙なため、一度ゲームを起動したら、一瞬のうちにスタミナの消費を終えてゲームを終了しなければなりません。 すなわち、時刻 T_i にスタミナが s だけ残っていた場合、あなたはスタミナを s 以下の任意の非負整数量消費し、消費した分だけすぬけ君の知力を上げる操作をすることができますが、 それ以外の操作はできません。

現実の予定というのはなかなか決まらないもので、あなたは自分がこれから先しばらくどれほど忙しいのかを読み切れずにいます。そこで、各 K=1,2,...,N について、 N 個のゲームの起動時刻の候補のうち K 個以下を選んでゲームを起動する場合に、最終的にすぬけ君の知力が最大でいくつになるのかを計算することにしました。 これらの N 個の値をすべて求めてください。

制約

• 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)
• 入力はすべて整数である

入力例 1

3 3
2
4
6

出力例 1

3
6
7

K=1 のとき、時刻 4 にスタミナを 3 消費すればよいです。

K=2 のとき、時刻 2 にスタミナを 3 消費し、時刻 6 にスタミナを 3 消費すればよいです。

K=3 のとき、時刻 2 にスタミナを 3 消費し、時刻 4 にスタミナを 2 消費し、時刻 6 にスタミナを 2 消費すればよいです。

入力例 2

5 4
4
5
7
8
11

出力例 2

4
8
11
11
11

入力例 3

7 5
2
4
10
12
13
17
20

出力例 3

5
10
15
18
20
22
22