题目描述

一群 $N$ 个海盗发现了 $K$ 枚金币。他们必须决定如何分配这些金币。大家达成了以下规则：

年龄最大的海盗提出一个分配方案。（你可以假设所有海盗年龄都不同。）分配方案给每个海盗分配一个非负整数金币数，且这些金币数加起来正好是 $K$。

然后，每个海盗会对这个方案投赞成票（yes）或反对票（no）。方案通过所需的赞成票数取决于海盗人数。如果有 $X$ 个海盗，则需要 $V[X]$ 个 yes 票才能通过方案。如果方案通过，金币按照方案分配，过程结束。否则，年龄最大的海盗被扔下船，剩下的海盗重复这个过程。

海盗们的行为遵循以下规则。规则按优先级排列；比如规则 $2$ 只在规则 $1$ 无法区分多个最优选项时才用。

1. 海盗会尽力避免自己被扔下船。

2. 海盗会尽量让自己拿到更多金币。

3. 海盗会尽量让更多海盗被扔下船（除了自己，因为规则 $1$ 优先）。

4. 海盗会尽量让年龄最大的海盗拿到更多金币。如果还有多个选择符合以上规则，会依次让第二大、第三大海盗拿更多金币，以此类推。

如果多个方案在这些规则下都最优，海盗会随机选择一个。（你可以假设这不会影响最终答案。）此外，所有海盗都非常理性，且完全了解题目中的所有信息。他们不会结盟或合作，因为彼此不信任。

我们将海盗编号从 $1$ 到 $N$，编号从最年轻的海盗（$1$）到最年长的海盗（$N$）。

如果只有 $i$ 个海盗（其中 $i = 1, \dots, N$），那么最年长的海盗能拿到多少金币？

输入格式

第一行输入一个数字 $N\ (2 \le N \le 10^6)$。

第二行输入一个整数 $K\ (1 \le K \le 10^{18})$。

接下来 $N$ 行，每行输入 $V[i]\ (1 \le V[i] \le i)$，表示当剩下 $i$ 个海盗时，方案通过所需的 yes 票数。

本题 $25$ 分中有 $5$ 分的测试点满足 $N \le 2\,000$。

另外 $5$ 分的测试点满足 $\max(1, i - 3) \le V[i] \le i$ 对所有 $i = 1, \dots, N$ 成立。

再有 $5$ 分的测试点满足 $K = 10^{18}$。

输出格式

输出 $N$ 行整数。第 $i^{th}$ 行输出第 $i^{th}$ 个海盗如果是最年长海盗时能拿到的金币数；换句话说，如果只有 $1, \dots, i$ 个海盗存在时的结果。如果第 $i^{th}$ 个海盗被扔下船，则在第 $i^{th}$ 行输出 $-1$。

5
100
1
1
2
2
3

100
100
99
99
98

5
100
1
2
3
4
4

100
-1
-1
-1
100

4
100
1
1
2
3

100
100
99
97

4
2
1
1
2
3

2
2
1
-1

提示

样例 $1$ 解释

当剩 $2$ 个海盗时，海盗 $2$ 可以提议把所有金币都给自己。只需 $1$ 票通过，他自己投赞成票，方案必定通过。

当剩 $3$ 个海盗时，海盗 $3$ 需要至少一个人支持他。他可以给海盗 $1$ 一枚金币，自己拿 $99$ 枚。海盗 $1$ 知道如果方案不通过，他将一文不名，所以给他一枚金币足够让他投赞成票。

当剩 $4$ 个海盗时，海盗 $4$ 给海盗 $2$ 一枚金币，自己拿 $99$ 枚。

当剩 $5$ 个海盗时，海盗 $5$ 给海盗 $1$ 和海盗 $3$ 各一枚金币，自己拿 $98$ 枚。

样例 $2$ 解释

这次，除了 $5$ 个海盗时只需 $4$ 票通过外，其他情况都需要全票通过。

如果需要全票通过，且海盗数 $\ge2$，最年轻的海盗会投反对票，既能最大化自己的金币，也能让更多海盗被扔下船。

当有 $5$ 个海盗时，最年长的海盗会提议把 $100$ 金币全给自己。除了最年轻的海盗，其他人都会投赞成票，因为如果方案不通过，最年轻的海盗会把他们全部扔下船，自己独享金币。海盗们不想被扔下船，虽然没分到金币，还是投赞成票。

样例 $3$ 解释

前三种情况在样例输入 $1$ 中已有解释。$4$ 个海盗时，最年长的海盗需要 $3$ 票通过。他会给最年轻的海盗 $2$ 枚金币，给第二年轻的海盗 $1$ 枚，自己拿剩下的金币。

样例 $4$ 解释

情况和示例 $3$ 相同，但金币只有 $2$ 枚。$1$、$2$、$3$ 个海盗时情况和示例 $3$ 一样。

$4$ 个海盗时，最年长的海盗没有足够金币争取 $3$ 票通过，结果被扔下船。

翻译来源：GPT 4.1 mini。