|
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Входные данные
В первой строке входного файла находятся три числа:
N
– количество занятых мест в зале (целое положительное число,
не превышающее 10 000),
M
– количество рядов (целое положительное число, не превышающее 100 000) и
K
– количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих
N
строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения
M
, а второе –
K
).
Выходные данные
Два целых положительных числа: наибольший номер ряда
и наибольший номер места в найденной паре кресел.
Типовой пример организации данных во входном файле
7 7 8
1 1
6
6
5
5
6 7
4
4
2 2
3 3
При таких исходных данных
ответом является пара чисел 5 и 8. Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.
Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаем
ого
файл
а.
|