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