P13512 [KOI 2025 #1] 稻草人

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

一支带有力量 $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$ | $-1$ | 不可能 | | $i=3$ | $3$ | $[1, 2, 3]$ | | $i=4$ | $3$ | 可选择 $[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)$ 的值，以空格分隔。

### 限制条件 * 给定的所有数都是整数。 * $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 分) 无附加限制条件。