26_0263

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

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

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

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

Входные данные

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

Выходные данные

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

Учебный пример организации данных во входном файле

3 6 3
1 1
3 2
5 3

Корабль размещается в ряду 6, вертикальном ряду 1. До ближайшего корабля сверху остаётся 4 свободных клеток. Размещения с большим числом свободных клеток сверху нет. Ответ для учебного примера: 6 4.

Учебный пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

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

• 26_0263.txt