Задание №5270

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

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

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

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

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

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

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

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

7 6 6

2 1

2 4

4 2

5 3

6 1

4 5

5 6

При таких исходных данных ответом является пара чисел 4 и 3.

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