26_0300

Задание выполняется с использованием прилагаемых файлов.

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры,
в отличие от классической, допускается увеличение количества и длины кораблей,
а игровое поле может быть прямоугольным, размером $M \times K$, где $M$ —
количество горизонтальных рядов клеток на игровом поле (целое положительное
число, не превышающее $100,000$), $K$ — количество вертикальных рядов клеток
на игровом поле (целое положительное число, не превышающее $100,000$).
Нумерация горизонтальных рядов поля идёт сверху вниз с $1$, а вертикальных —
слева направо также с $1$. Некоторые клетки поля уже заняты кораблями
($n$-палубный корабль занимает, соответственно, $n$ подряд идущих клеток).

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

Если в найденном для размещения корабля ряду мест, удовлетворяющих условию,
несколько, то найдите место с наименьшими номерами вертикальных рядов.
Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.

Входные данные.
В первой строке входного файла находятся три числа: $N$ — количество клеток
игрового поля, в которых расположены однопалубные корабли или части
многопалубных кораблей ($N$ — целое положительное число, не превышающее
$100,000$), $M$ — количество горизонтальных рядов игрового поля и $K$ —
количество вертикальных рядов игрового поля. В следующих $N$ строках
соответственно находятся пары натуральных чисел: номер горизонтального ряда
и номер вертикального ряда игрового поля, в которых расположены корабли или
их части (первое число не превышает значения $M$, а второе — $K$).

Запишите в ответе два целых числа: номер горизонтального ряда и наименьший
из двух номеров вертикальных рядов, где необходимо разместить корабль.

Файлы к заданию:

• 26_0300.txt