题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

一支带有力量 $P$ 的箭从数轴上的位置 0 向右方发射。在每个整数位置 $i$ ($1 \le i \le N$)，最多可以设置一个防御力为 $A_i$ 的稻草人。当箭撞到稻草人时，如果箭的力量小于或等于稻草人的防御力，箭会立即停止。反之，如果箭的力量大于防御力，箭的力量会减去 $A_i$ 并继续前进。

对于整数 $i$，我们将 $f(i)$ 的值定义为“为了使箭在位置 $i$ 或其左侧停止所需要的稻草人的最小数量”。如果无法使箭停止，则值为 $-1$。

例如，假设 $N=5, P=10$ 并且 $A_1=3, A_2=6, A_3=1, A_4=1, A_5=10$。所有 $f(i)$ 的值和安装的稻草人的位置如下表所示。

$i$	$f(i)$ 的值	安装的稻草人的位置
$i=1$	$-1$	不可能
$i=2$
$i=3$	$3$	$[1, 2, 3]$
$i=4$		可选择 $[1, 2, 3]$ 或 $[1, 2, 4]$ 之一
$i=5$	$1$	$[5]$

请编写一个程序，求出对于所有 $1 \le i \le N$ 的 $i$ 的 $f(i)$ 值。

输入格式

第一行给定整数 $N$ 和箭的力量 $P$，以空格分隔。

第二行给定 $N$ 个整数 $A_1, A_2, \cdots, A_N$，以空格分隔。

输出格式

在第一行输出 $f(1), f(2), \cdots, f(N)$ 的值，以空格分隔。

5 10
3 6 1 1 10

-1 -1 3 3 1

3 10
20 20 20

1 1 1

1 5
3

-1

提示

限制条件

• 给定的所有数都是整数。
• $1 \le N \le 500,000$
• $1 \le P \le 10^9$
• 对于每个 $1 \le i \le N$ 的 $i$，都有 $1 \le A_i \le 10^9$。

子任务

1. (4 分) $N \le 8$
2. (8 分) $N \le 5000$
3. (8 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i = 1$。
4. (20 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i = 2$ 或 $A_i = 3$。
5. (40 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i \le 50$。
6. (40 分) 对于所有 $1 \le i < N$ 的 $i$，$A_i \le A_{i+1}$。
7. (30 分) 无附加限制条件。