有 $n$ 个商品，第 $i$ 个商品的体积为 $a_i$。你有若干个容量为 $L$ 的背包。

在第 $i$ 天，你希望将所有编号为 $i, i+1, \cdots, n-1, n$ 的物品装入背包带走。你将物品装入背包的策略为，依次对每个物品 $k=i,i+1,\cdots, n$：

• 如果当前背包剩余容量大于等于 $a_k$，则将该物品装入背包。
• 否则，则将该背包带走，并拿出一个全新的背包，回到第一步。

你想要知道，对每个 $i=1,2,\cdots, n$，所需背包的数量 $f_i$ 是多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $L$。

接下来一行，包含 $n$ 个整数 $a_1,a_2,\cdots, a_n$.

输出格式

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

样例数据

6 3
1 2 2 2 1 2

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$。