经过数月的航行且屡遭挫折，Floating Point 号海盗船的船员们偶然发现了一批由 $m$ 枚相同的金币组成的宝藏。于是他们决定瓜分宝藏并结束航行。

在航行过程中，海盗们已经彼此了解。他们都知道所有海盗都具备完美的逻辑思维能力（其中许多人最初的职业生涯就是从破解软件安全防护开始的），并且主要受贪婪驱动，尽管有些海盗比其他人更贪婪。此外，船上还确立了明确的线性等级制度——海盗们被编号为 $1$ 到 $n$。

海盗们使用传统的“海盗技术”来瓜分宝藏。编号最小的海盗（在尚未被扔下船的海盗中）提出一种宝藏分配方案，即为每一位尚未被扔下船的海盗 $i$ 指定 $b_i$，表示该海盗在提议方案中将获得的金币数量（所有 $b_i$ 的总和为 $m$）。随后，所有海盗（包括提议者）对该方案进行投票。如果至少有 $50\%$ 的海盗投票赞成，则宝藏按提议分配。否则，提议分配的海盗将被扔下船，不再参与后续谈判，也不会获得任何金币。之后，该程序重复进行（等级制度中的下一位海盗向剩余的海盗提出分配方案）。

每一位海盗 $i$ 在以下情况下会投票赞成提议的方案： 如果拒绝该方案，他会在提出自己的方案后被扔下船； 或者 $b_i \ge d_i + a_i$，其中 $d_i$ 是如果拒绝该方案后该海盗本应获得的金币数量，$a_i$ 是他的贪婪系数。

所有海盗都知晓所有人的贪婪系数，并且知道每个人在选择时都会遵循以下确定性策略： 如果不存在任何可接受的分配方案（即至少有一半尚未被扔下船的海盗会接受的方案），则该海盗提议自己拿走全部宝藏。随后，他接受自己的命运，被扔下船。 如果存在可接受的分配方案，则会提出其中一种（获得 $0$ 枚金币也比被扔下船要好）。 在多种可能的方案中，海盗会选择自己能保留最多金币的那一种。 海盗倾向于将之前的失败归咎于等级制度中更靠前的海盗，因此如果分配方案仍然不唯一，他们更倾向于给编号更大的海盗分配更多的金币。具体来说：海盗 $i$ 在所有可接受的方案中进行选择时，会依次最小化：海盗 $i+1$ 获得的金币数量，然后是海盗 $i+2$ 获得的金币数量，以此类推。

你的任务是编写一个程序，根据上述规则确定每位海盗将获得多少金币。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50\,000, 1 \le m \le 5\,000\,000$)，分别表示海盗的人数和待分配的金币数量。

第二行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 64$)，表示各海盗的贪婪系数。

输出格式

输出一行，包含 $n$ 个整数 $b_1, b_2, \dots, b_n$。如果第 $i$ 位海盗在执行题目描述的程序后被扔下船，则 $b_i = -1$；否则 $b_i$ 表示第 $i$ 位海盗获得的金币数量。

样例

样例输入 1

3 100
28 1 56

样例输出 1

44 0 56

样例输入 2

5 1
1 1 1 1 1

样例输出 2

-1 0 0 1 0

样例输入 3

6 6
3 5 1 4 2 6

样例输出 3

2 0 0 0 4 0

说明 1

在第一个样例中，有三名海盗：Algor、Bajtazar 和 Char。如果 Algor 被扔下船，Bajtazar 将进行分配，他会拿走全部 $100$ 枚金币，而 Char 什么也得不到。虽然 Char 不会接受这样的方案，但他会被 Bajtazar 投票否决。

因此，Algor 无法以任何方式说服 Bajtazar 投票赞成（他必须至少提供 $100+1$ 枚金币）。因此，他需要通过给 Char 提供足够多的金币（具体来说至少是 $0+56$）来说服 Char。因此，Algor 给 Char $56$ 枚金币，自己留下 $44$ 枚——Algor 和 Char 将投票赞成该方案，从而否决了 Bajtazar。

在第二个样例中，第一位海盗拥有的金币太少，无法满足足够多的海盗。因此他提议自己拿走一枚金币，随后被扔下船。第二位海盗有两种可接受的分配方案。他可以给第三位或第四位海盗一枚金币——根据规则，他选择了后者。

在第三个样例中，第一位海盗提出的方案得到了编号为 $1, 2$ 和 $5$ 的海盗的赞成。