B

B-Домино
Полный балл:	30
Бонусные баллы:
Ограничение времени:	2 с
Ограничение памяти:	256M
Домино
Вася установил на телефон игру, где в каждой клетке полоски размером 2×N записано целое число. Цель игры состоит в том, чтобы накрыть часть клеток доминошками размерами 2×1 так, чтобы сумма чисел на не покрытых доминошками клетках была минимальной.

Доминошки можно поворачивать горизонтально или вертикально, они не могут накладываться. Обязательно использовать все имеющиеся доминошки.

Формат входных данных
В первой строке вводится два числа N и K (1 ≤ N ≤ 2×105, 0 ≤ K ≤ 2×105, 0 ≤ N × K ≤ 2 × 105, N ≥ K) — размер полоски и количество имеющихся доминошек.

В следующих N строках вводятся по 2 целых числа, записанных на полоске. Числа не превосходят 109 по модулю.

Формат результата
Выведите N строк по 2 числа в каждой — описание расположения доминошек на полоске. Каждая клетка должна описываться либо числом от 1 до K — номером доминошки, которой она накрыта, либо числом 0, в случае, если она не накрыта доминошкой.

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

Примеры
Входные данные
3 2
2 2
3 3
2 1
Результат работы
0 1
2 1
2 0
Входные данные
2 1
1 2
3 4
Результат работы
0 0
1 1
Примечания
Система оценки: Решения, верно работающие при N ≤ 20 будут получать не менее 50% баллов.