После многомесячного и полного неудач плавания пираты с корабля 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

44 0 56

Пример 2

5 1
1 1 1 1 1

-1 0 0 1 0

Пример 3

6 6
3 5 1 4 2 6

2 0 0 0 4 0

Примечание

В первом примере у нас есть три пирата: Алгор, Байтазар и Чар. Если бы Алгор был выброшен за борт, то Байтазар совершил бы раздел, в котором сам получает все 100 монет, а Чар ничего не получает. Хотя Чар не принял бы такого решения, он был бы переголосован Байтазаром.

В связи с этим Алгор никоим образом не в состоянии убедить Байтазара голосовать «за» (ему пришлось бы предложить ему по меньшей мере $100 + 1$ монет). Следовательно, ему нужно убедить Чара, дав ему достаточно много монет (а конкретно по меньшей мере $0 + 56$). В связи с этим Алгор предлагает 56 монет Чару, а 44 монеты оставляет себе — Алгор и Чар проголосуют за такой раздел, переголосовав Байтазара.

Во втором примере у первого пирата слишком мало золотых монет для раздела, чтобы удовлетворить достаточно много пиратов. Поэтому он предлагает, что возьмет монету себе, после чего его выбрасывают за борт. Второй пират имеет на выбор два раздела, которые являются приемлемыми. Он может дать монету третьему или четвертому пирату — в соответствии с правилами он выбирает второй раздел.

В третьем примере за раздел, предложенный первым пиратом, проголосовали пираты с номерами 1, 2 и 5.