问题描述

你正在享受"养可爱猫咪"的乐趣。为了让你心爱的猫咪尽可能聪明，你决定对它进行智力训练。

在"养可爱猫咪"中，你可以消耗"体力"来训练猫咪的智力。每消耗1点体力，猫咪的智力就会提升1点。

体力每单位时间回复1点，最多回复到X点。当体力达到上限X时，体力不会随时间恢复。同时，体力不能低于0点。初始状态下，在时刻O，体力已经满了，即积攒了X点体力。

当然，如果体力积攒起来后立即使用是最有效的方式，但不幸的是你在现实世界中有一些事情要处理，不能一直玩"养可爱猫咪"（现实生活通常不那么灵活）。

尽管如此，你还是想在繁忙的生活中找到一些时间来启动"养可爱猫咪"游戏。你列出了N个可用于启动游戏的时间候选项。第i个候选是时刻Ti。由于你很忙，一旦启动游戏，你必须立即消耗完体力并结束游戏。也就是说，如果在时刻Ti仍有s点体力，你可以消耗s以下的任意非负整数，并提升猫咪的智力相应的点数，但不能进行其他操作。

由于真实计划往往不容易确定，你无法预测接下来的一段时间内有多忙。因此，你决定计算以下情况：在从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)$
• 所有输入都是整数

输入

输入从标准输入给出，具体格式如下：

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

输出

对于每个$K=1,2,...,N$，输出猫咪最终智力的最大值。

示例输入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