Картки#1867

Картки

1 секунда

256 мегабайтів

Легка

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

Людмила Петрівна легко розв'язала цю задачу, а ти зможеш?

Вхідні дані

У першому рядку містяться числа $N$ та $K$ ( $1 \leq N \leq 100000$ 1 \leq N \leq 100\ 000, $1 \leq K \leq N$ 1 \leq K \leq N) — кількість карт та максимально припустима різниця. Кожний з наступних $N$ рядків описує одну карту — два цілих числа: перше написав Вася з одного боку, друге — Петя з іншого. Вася і Петя не знають чисел, модуль яких перевищує $1 0^{9}$ 10^9.

Вихідні дані

У першому рядку виведіть одне число — максимально можливу суму. Далі виведіть $N$ чисел: для кожної карти виведіть 1, якщо догори петин бік, і 0, якщо догори васин.

Якщо існує декілька відповідей, виведіть будь-яку з них.

Приклади

Приклад 1