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

Людмила Петровна легко справилась с задачей, а Вы сможете?

Входные данные

В первой строке содержатся числа N и K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) — количество карточек. Далее в N строках содержится описание карточек — два целых числа: первое число написано Васей на одной стороне карточки, второе написано Петей на другой стороне. Вася и Петя не знают чисел, которые по модулю превосходят 109.

Выходные данные

В первой строке выходного файла должно содержатся одно число — максимально возможная сумма. Далее выведите N чисел — для каждой карточки выведите 1, если она Петиной стороной, и 0, если Васиной.

Если ответов несколько, выведите любой.