一群海盗发现了 $K$ 枚金币。他们必须决定如何分配这些金币。他们约定了以下规则：
最年长的海盗提出一种分配方案。（你可以假设所有海盗的年龄各不相同。）分配方案为每位海盗分配非负整数数量的金币，使得总和等于 $K$。
然后，每位海盗对该方案投“赞成”或“反对”票。提案通过所需的“赞成”票数取决于海盗的总人数。如果有 $X$ 位海盗，则提案通过需要 $V[X]$ 张“赞成”票。如果提案通过，金币将按照提议的方案进行分配，过程结束。否则，最年长的海盗将被扔进海里，并由剩下的海盗重复上述过程。
海盗们根据以下规则行事。规则按优先级排序；例如，规则 2 仅用于区分根据规则 1 判定为同等最优的多个选项。
- 海盗会采取行动防止自己被扔进海里。
- 海盗会采取行动以最大化他获得的金币数量。
- 海盗会采取行动以最大化被扔进海里的海盗人数（不包括他自己，因为规则 1 优先级更高）。
- 海盗会采取行动以最大化最年长海盗获得的金币数量。如果仍有多个符合上述规则的选项，他将最大化第二年长海盗获得的金币，以此类推。
如果根据这些规则存在多个最优选项，则海盗会随机选择一个行动。（你可以假设本问题的答案在这种情况下不依赖于海盗的选择。）此外，所有海盗都完全理性，并知晓本问题描述中包含的所有信息。由于互不信任，他们无法达成协议或结盟。
我们将海盗编号为 $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$ 位海盗时，提案通过所需的“赞成”票数 ($i = 1, \dots, N$)。
输出格式
输出应包含 $N$ 个整数，每行一个。第 $i$ 行的输出是如果第 $i$ 位海盗是当时最年长的海盗（即只有海盗 $1, \dots, i$ 存在）时，他能获得的金币数量。如果第 $i$ 位海盗被扔进海里，则在第 $i$ 行输出 -1。
样例
样例输入 1
5 100 1 1 2 2 3
样例输出 1
100 100 99 99 98
说明 1
如果剩下 2 位海盗，海盗 2 可以提议将所有金币给自己。该提案只需要 1 张赞成票即可通过，因此他可以通过投赞成票来确保提案通过。
如果剩下 3 位海盗，海盗 3 需要其他人投赞成票。他可以通过给海盗 1 分配 1 枚金币，自己留下 99 枚来确保这一点。海盗 1 知道如果提案不通过，他将一无所获。因此，一枚金币足以获得他的选票。
如果剩下 4 位海盗，海盗 4 给海盗 2 分配 1 枚金币，自己留下 99 枚。
如果剩下 5 位海盗，海盗 5 给海盗 1 和海盗 3 各分配 1 枚金币，自己留下 98 枚。
样例输入 2
5 100 1 2 3 4 4
样例输出 2
100 -1 -1 -1 100
说明 2
在这种情况下，提案通过需要全体一致同意，除非剩下 5 位海盗，此时 5 票中只需要 4 票即可通过。
如果需要全体一致同意，且剩下 2 位或更多海盗时，最年轻的海盗会投反对票，以最大化自己的金币并尽可能多地将海盗扔进海里。
在剩下 5 位海盗的情况下，最年长的海盗会提议给自己 100 枚金币。除了最年轻的海盗外，所有人都会投“赞成”，因为如果提案不通过，最年轻的海盗会将所有人扔进海里，并在只剩下他自己时拿走所有金币。由于海盗们不想被扔进海里，他们会投“赞成”，即使最年长的海盗不给他们任何金币。
样例输入 3
4 100 1 1 2 3
样例输出 3
100 100 99 97
说明 3
前三种情况已在样例 1 中解释。
当剩下 4 位海盗时，最年长的海盗需要 3 张赞成票。他会给最年轻的海盗 2 枚金币，给第二年轻的海盗 1 枚金币，其余留给自己。
样例输入 4
4 2 1 1 2 3
样例输出 4
2 2 1 -1
说明 4
情况与样例 3 相同，但现在只有 2 枚金币。对于 1、2 或 3 位海盗，情况与样例 3 相同。
对于 4 位海盗，最年长的海盗没有足够的金币来确保他所需的 3 张赞成票，因此他会被扔进海里。