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