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

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

Вхідні дані

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

Вихідні дані

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

Якщо відповідей декілька, виведіть довільну.