配点 : 500 点
問題文
您正在享受“Snuke Sodate”。您想让您心爱的斯努克成为最聪明的猫,因此您决定对他进行一些大脑训练。
在《Snuke Sodate》中,你可以花费“体力”来训练Snuke的智力。耐力 1 每消耗一次,斯努克的智力就会增加。 它将上涨 1 。
耐力为1 每单位时间 最多只有 1 恢复到 X 。最大耐力 如果您已达到 X ,您的体力将不会随着时间的推移而恢复。 还有体力 不能小于 0 。初始状态,即时间 在 O 时,体力已满,即 仅累积了 X 。
当然,体力积累起来就消耗是最有效率的,可惜你在现实世界还有事情要做。 你不能一直玩“Snuke Figure”(现实生活往往是不灵活的)。
不过,您也许可以在忙碌的生活中抽出时间来推出“Snuke Sodate”。 N 我想出了一些。i 第二个候选者是时间 T_i 。 因为你太忙了,一旦开始游戏,你就得立刻消耗完体力并退出游戏。 也就是说,时间 T_i 有耐力 如果你还剩下 s ,你就会失去体力。 s 你可以消耗以下任意非负整数数量,并根据消耗的数量增加 Snuke 的智力。 无法进行其他操作。
现实生活中的计划很难实现,你可能无法掌握未来一段时间你会有多忙。因此,每个 K=1,2,...,N , 当我输入 N 游戏发布时间候选 如果你选择 K 或更少并开始游戏,我们决定计算Snuke最终的最大智力是多少。 这些 查找所有 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 ,输出Snuke智力的最终最大值。
入力例 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