Задание №5269

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

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

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

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

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

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

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

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

6 6 8

1 1

5 5

5 6

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 4 и 8. Условию задачи удовлетворяет расположение корабля в вертикальных рядах 6, 7 и 8 игрового поля в горизонтальном ряду 4.

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