#P2441. 死亡日记

死亡日记

你收到了一个名为Death Note的笔记本。这款笔记本拥有无限数量的页面。规则写在这个笔记本的最后一页(呵呵)。它说:“你必须连续n天在这个笔记本上写名字。第i天,你必须写出ai个名字。”你很害怕(当然你害怕,谁收到一个名为死亡笔记的笔记本,并写有一些奇怪的规则,都会害怕的 )。

 

当然,你决定遵循这条规则。当你平静下来时,你想出了一个如何在笔记本中写名字的策略。你已计算出笔记本的每个页面都可以包含m个名字。

你将从第一页开始编写名字。只要不超过此页面上的名字限制,你就会在当前页面上写入名字。当前页面结束时翻页。

请注意,你总是在页面结束时翻页,如果是最后一天也无关紧要。如果在某一天之后当前页面仍然可以保留至少一个名字,那么在第二天你将继续从当前页面写入名字。

 

现在你对每天会翻页多少次感兴趣。

Input

输入的第一行包含两个整数n和m(1 < n < 1e5, 1 <= m <= 1e9) - 你将在笔记本中写入名称的天数以及可以在笔记本的每个页面上写入的名称的数量。

第二行包含n整数a1,a2,a3...an(1 <= ai <= 1e9),表示在第i天你将在笔记本中写的名字数。

Output

输出每一天翻页的次数。如果刚好写完一页翻页次数也要加1。

 

Sample Input

3 5
3 7 9

Sample Output

0 2 1

HINT

Source