数ヶ月にわたる不運な航海の末、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$ が受け取る金貨の数、というように続きます。

あなたの課題は、上記のルールに従って、各海賊が何枚の金貨を受け取るかを決定するプログラムを書くことです。

入力

最初の行には、2つの整数 $n$ と $m$ ($1 \le n \le 50\,000, 1 \le m \le 5\,000\,000$) が含まれており、それぞれ海賊の数と分配する金貨の数を表します。 2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 64$) の列が含まれており、各海賊の強欲係数を表します。

出力

出力には、$n$ 個の整数 $b_1, b_2, \dots, b_n$ を含む1行を出力してください。もし $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

注記

例の解説：最初の例には、Algor、Bajtazar、Charの3人の海賊がいます。 もしAlgorが船から追い出された場合、Bajtazarが分配を行い、彼自身が100枚の金貨をすべて受け取り、Charは何も受け取りません。Charはこの解決策を受け入れないでしょうが、Bajtazarによって否決されます。 そのため、AlgorはBajtazarを賛成に回らせる方法がありません（少なくとも $100 + 1$ 枚の金貨を提案しなければならないため）。したがって、彼はCharを説得するために十分な金貨（具体的には少なくとも $0 + 56$ 枚）を与える必要があります。その結果、AlgorはCharに56枚の金貨を提供し、自分は44枚を残します。AlgorとCharはこの分配案に賛成し、Bajtazarを否決します。

2番目の例では、最初の海賊は十分な数の海賊を満足させるための金貨を十分に持っていません。そのため、彼は自分自身のために1枚の金貨を取ると提案し、その後船から追い出されます。2番目の海賊には、受け入れ可能な2つの分配案の選択肢があります。彼は3番目または4番目の海賊に金貨を与えることができますが、ルールに従って後者の分配案を選択します。

3番目の例では、最初の海賊によって提案された分配案に対して、番号1、2、および5の海賊が賛成しました。