题目描述
一支带有力量 $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
输入 #1
5 10
3 6 1 1 10输出 #1
-1 -1 3 3 1输入输出样例 #2
输入 #2
3 10
20 20 20输出 #2
1 1 1输入输出样例 #3
输入 #3
1 5
3输出 #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$。
子任务
- (2 分) $N \le 8$
- (4 分) $N \le 5000$
- (4 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i = 1$。
- (10 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i = 2$ 或 $A_i = 3$。
- (30 分) 对于所有 $1 \le i \le N$ 的 $i$，$A_i \le 50$。
- (30 分) 对于所有 $1 \le i < N$ 的 $i$，$A_i \le A_{i+1}$。
- (20 分) 无附加限制条件。