T1 远行

题目信息

时间限制: 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$