You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目信息

时间限制: 1s

空间限制: 512M

输入文件: pack.in

输出文件: pack.out

题目描述 U 是个爱旅行的人，U 有 $n$ 件旅行用品，编号从 $1$ 到 $n$，第 $i$ 件用品的体积为 $a_i$。

视旅途远近，U 会选择一个 $j$，并在这次旅行中将编号为 $j, j+1, \dots, n$ 的用品收纳进若干体积为 $L$ 的小背包带走，U 的收纳逻辑如下：

依次考虑每个用品 $k=j,j+1,\dots, n$

如果当前小背包剩余容量大于等于 $a_k$，则将该物品装入小背包。

否则，拿出一个全新的背包。

那么对每个 $j=1,2,\dots, n$，所需背包的数量 $f_j$ 是多少呢？

输入格式

输入的第一行包含两个整数 $n$ 和 $L$，含义如题所示

接下来一行，包含 $n$ 个整数 $a_1,a_2,\dots, a_n$，表示每个用品的体积

输出格式

输出一行 $n$ 个整数 $f_1,f_2,\dots, f_n$，表示答案

样例

样例输入 1

6 3

1 2 2 2 1 2

样例输出 1

4 4 3 2 1 1

数据范围与提示

对于所有数据，$1 \le n \le 2 \times 10^5$，$1 \le L \le 10^9$，$1 \le a_i \le L$。

| 子任务编号 | 特殊性质 | 分值 |

| $1$ | $n \le 1,000$ | $25$ |

| $2$ | 所有的 $a_i$ 均相等 | $20$ |

| $3$ | $a_i$ 在 $[1, L]$ 内均匀随机生成 | $30$ |

| $4$ | 没有额外的限制 | $25$ |