經過數個月充滿挫折的航行後，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

說明 1

在第一個範例中，有三位海盜：Algor、Bajtazar 和 Char。如果 Algor 被丟下船，Bajtazar 將進行分配，他會拿走全部 $100$ 枚金幣，而 Char 什麼也得不到。雖然 Char 不會接受這樣的方案，但他會被 Bajtazar 否決。

因此，Algor 無法以任何方式說服 Bajtazar 投贊成票（他必須提議給他至少 $100 + 1$ 枚金幣）。因此，他需要透過給予 Char 足夠多的金幣（具體來說至少 $0 + 56$ 枚）來說服 Char。因此，Algor 提供 $56$ 枚金幣給 Char，並留下 $44$ 枚給自己——Algor 和 Char 將投票贊成該方案，從而否決了 Bajtazar。

範例 2

5 1
1 1 1 1 1

輸出 2

-1 0 0 1 0

說明 2

在第二個範例中，第一位海盜擁有的金幣不足以滿足足夠多的海盜。因此，他提議自己拿走一枚金幣，隨後被丟下船。第二位海盜有兩種可接受的分配方案可供選擇。他可以給第三位或第四位海盜一枚金幣——根據規則，他選擇後者。

範例 3

6 6
3 5 1 4 2 6

輸出 3

2 0 0 0 4 0

說明 3

在第三個範例中，編號為 $1, 2$ 和 $5$ 的海盜對第一位海盜提出的方案投了贊成票。