Домино
вася установил на телефон игру, где в каждой клетке полоски размером 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, в случае, если она не накрыта доминошкой.
если ответов несколько — выведите любой из них.
