题目描述

译自 CCO 2016 Day2 T3「Pirates」。

一群有 $N$ 个海盗找到了 $K$ 枚金币。他们必须决定如何分配这些金币。他们按照以下规则分配：

年龄最大的海盗提出一个分配方案。每个海盗得到的金币数量必须是非负整数，并且总和等于 $K$。

然后，每个海盗对这个提议投票「同意」或「不同意」。提议通过所需的同意票数取决于海盗的数量。如果有 $X$ 个海盗，那么需要 $V_X$ 张同意票才能通过提议。如果提议通过，金币按照提议的分配方案分配，游戏结束。否则，年龄最大的海盗被扔下船，游戏重新开始。

海盗们按照以下规则行动，这些规则按优先级排列：

1. 海盗会采取行动避免自己被扔下船。
2. 海盗会尽可能多地获得金币。
3. 海盗会尽可能多地让其他人（除了自己，因为规则 $1$ 优先）被扔下船。
4. 海盗会尽可能多地让年龄最大的海盗获得金币。如果有多个选择符合这些规则，他会最大化第二老的海盗得到的金币，然后是第三老的海盗，以此类推。

如果有多个选项符合这些规则，海盗会随机选择一个行动。（你可以假设这个问题的答案不依赖于海盗在这个情况下的选择。）此外，所有海盗都非常聪明，知道问题描述中的所有信息。他们不能达成协议或联盟，因为他们不信任彼此。

我们将海盗从 $1$ 到 $N$ 编号，其中 $1$ 是最年轻的，$N$ 是最老的。

如果有 $i\ (1\leq i\leq N)$ 个海盗，他们中最老的海盗能得到多少金币？

输入格式

输入的第一行是包含一个整数 $N$。

输入的第二行是包含一个整数 $K$。

接下来的 $N$ 行，每行包含一个整数 $V_i$，表示如果有 $i$ 个海盗，通过提议所需的同意票数。

输出格式

输出 $N$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个海盗如果是最老的海盗（即只有海盗 $1, \ldots , i$ 存在时）能得到的金币数量。如果第 $i$ 个海盗被扔下船，在第 $i$ 行输出 $-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

数据范围与提示

对于 $20\%$ 的数据，$N \leq 2000$；
对于另外 $20\%$ 的数据，$\max(1, i-3) \leq V_i \leq i\ (1\leq i\leq N)$；
对于另外 $20\%$ 的数据，$K=10^{18}$；
对于 $100\%$ 的数据，$2 \leq N \leq 10^6,1 \leq K \leq 10^{18}$；$1 \leq V_i \leq i\ (1\leq i\leq N)$。