26_0252

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

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

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

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

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

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

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

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

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

7 7 8
1 1
2 2
3 3
4 4
5 5
6 6
6 7

Корабль можно разместить в ряду 5 на клетках с номерами 6, 7, 8. Эти клетки и клетки тех же вертикальных рядов выше корабля свободны. Ниже подходящего размещения нет. Ответ для учебного примера: 5 8.

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

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

• 26_0252.txt