← 返回题目列表

Codeforces · 1016/A

A. 死亡笔记

中文机器翻译题面 查看原题

你收到了一本叫做死亡笔记的笔记本。这本笔记本有无限页数。这本笔记本的最后一页(呵呵)写着一条规则。它说:“您必须在连续 $$$n$$$ 天内在此笔记本上写下姓名。在第 $$$i$$$ 日期间,您必须准确地写下 $$$a_i$$$ 姓名。”。你害怕了(当然你害怕了,如果他收到一个名为死亡笔记的笔记本,上面写着一些奇怪的规则,谁会不害怕?)。

当然,您决定遵循此规则。当你冷静下来后,你想出了一个如何在笔记本上写名字的策略。您已经计算出笔记本的每一页都可以包含精确的 $$$m$$$ 名称。您将从第一页开始写名字。只要不超过该页上姓名的数量限制,您就可以在当前页上书写姓名。当当前页面结束时,您翻页。请注意,您总是在结束时翻页,无论是否是最后一天。如果某一天之后当前页面仍然可以容纳至少一个名称,那么第二天您将继续从当前页面写入名称。

现在您对以下问题感兴趣:您每天会翻页多少次?您感兴趣的是每天从 $$$1$$$ 到 $$$n$$$ 翻的页数。

输入

输入的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — 您将在笔记本中书写姓名的天数以及笔记本每页上可书写的姓名数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 表示您将在第 $$$i$$$ 天在笔记本中写入的姓名数量。

输出

精确打印 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ 是您在第 $$$i$$$ 期间翻页的次数。

示例

输入 #1

3 5
3 7 9

输出 #1

0 2 1

输入 #2

4 20
10 9 19 2

输出 #2

0 0 1 1

输入 #3

1 100
99

输出 #3

0

注意

在死亡笔记的第一个示例页面中,将如下所示 $$$[1, 1, 1, 2, 2], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3], [3, 3, 3, 3]$$$。数组中的每个数字描述了相应位置上的名称将在哪一天被写入。很容易看出,您应该在第二天翻第一页和第二页,在第三天翻第三页。