Домино Вася установил на телефон игру, где в каждой клетке полоски размером 2×N записано целое число. Цель игры состоит в том, ч
Домино Вася установил на телефон игру, где в каждой клетке полоски размером 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, в случае, если она не накрыта доминошкой.