Gry 开始使用新的 Expify 音乐流媒体平台。由于 Gry 不想花钱，Expify 强制他收听广告。广告只能在某首歌曲播放结束后播放（不能在歌曲中间播放），且仅当距离上一次广告结束的时间至少为 $c$ 秒时才能播放。

Gry 有一个包含 $n$ 首歌曲的循环播放列表，其中第 $i$ 首歌曲的持续时间为 $d_i$ 秒。他想要最小化广告数量，因此他想知道，如果他从第 $i$ 首歌曲开始收听整个播放列表（即循环播放列表在播放 $n$ 首歌曲后停止），会有多少个广告。

我们假设在 Gry 开始收听之前有一个广告。这个广告以及播放列表停止后的那个广告都不计入总数。

输入格式

• 第一行包含播放列表中的歌曲数量 $n$ 和广告之间的刷新时间 $c$ ($1 \le n \le 10^6, 1 \le c \le 10^9$)。
• 第二行包含 $n$ 首歌曲的持续时间 $d_1 \dots d_n$ ($1 \le d_i \le 10^3$)。

输出格式

输出如果 Gry 从第 $i$ 首歌曲开始收听播放列表时，所产生的广告数量。

样例

样例输入 1

7 7
1 1 1 1 1 1 1

样例输出 1

0 0 0 0 0 0 0

样例输入 2

3 3
1 1 3

样例输出 2

0 1 1