题目描述

经过数月充满挫折的航行，来自「浮点号」的海盗们意外发现了一个宝藏，里面有 $m$ 枚相同的金币。他们决定分掉宝藏，结束航程。

在航行中，海盗们彼此熟悉。他们知道每个人都思维缜密（不少人是从破解软件防护开始海盗生涯的），而且大多贪婪无比，尽管贪心程度各有不同。他们还明确了从 $1$ 到 $n$ 的线性等级排序。

分宝藏时，海盗们沿用传统方式。当前未被扔下船的编号最小的海盗提出分配方案，为每个未被淘汰的海盗 $i$ 指定一个非负整数 $b_{i}$，表示他将分得的金币数（所有 $b_{i}$ 之和等于 $m$）。然后，所有海盗（包括提议者）投票赞成或反对。如果至少 $50\%$ 的海盗赞成，宝藏按提议分配；否则，提议者被扔下船，不参与后续讨论也分不到金币，下一位海盗继续提议。

海盗 $i$ 会赞成提议，如果反对会导致：

• 他自己在提议时被扔下船；
• 或 $b_{i} \geq d_{i} + a_{i}$，其中 $d_{i}$ 是反对后他能分到的金币数，$a_{i}$ 是他的贪婪系数。

所有海盗都知道彼此的贪婪系数，并遵循以下确定性策略：

• 若无任何可接受的分配（即无法被至少一半未淘汰海盗通过），提议者拿走全部宝藏，然后接受被扔下船的命运。
• 若有可接受的分配，他会提出其中一种（哪怕分 $0$ 币也比被扔下船好）。
• 在多种可接受提议中，他选择给自己留最多金币的方案。
• 海盗们倾向于责怪等级靠前的人，所以若仍有多选，他们优先给编号大的海盗多分金币。具体来说，海盗 $i$ 会依次最小化 $i+1$、$i+2$ 等海盗的分币数。

请你写一个程序，算出每个海盗最终分得多少金币。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 50000, 1 \leq m \leq 5000000)$，分别表示海盗数量和金币总数。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 64)$，表示各海盗的贪婪系数。

输出格式

输出一行，包含 $n$ 个整数 $b_{1}, b_{2}, \ldots, b_{n}$。若第 $i$ 个海盗被扔下船，则 $b_{i} = -1$；否则，$b_{i}$ 表示他分到的金币数。

3 100
28 1 56

44 0 56

在第一个样例中，有三个海盗：Algor、Bajtazar 和 Char。如果 Algor 被扔下船，Bajtazar 会提议自己拿全部 $100$ 枚金币，Char 得 $0$。虽然 Char 不会赞成，但 Bajtazar 一票足以通过。

因此，Algor 无法说服 Bajtazar（需给至少 $100+8$ 枚金币），只能拉拢 Char，给他至少 $0+56$ 枚金币。于是 Algor 提议自己拿 $44$ 枚，Char 拿 $56$ 枚，Algor 和 Char 赞成，压过 Bajtazar 的反对。

5 1
1 1 1 1 1

-1 0 0 1 0

在第二个样例中，第一个海盗金币太少，无法满足足够多的人。他提议自己拿 $1$ 枚，然后被扔下船。第二个海盗有两个可接受方案：给第三个或第四个海盗 $1$ 枚，按规则选后者。

6 6
3 5 1 4 2 6

2 0 0 0 4 0

在第三个样例中，第一个海盗的提议被编号 $1,2,5$ 的海盗赞成。