Места с открытым обзором
При покупке билетов на концерт известно, какие места в зале уже заняты. В зале рядов по мест в каждом; ряды нумеруются от сцены, нумерация рядов и мест ведётся с единицы. Соседними считаются места с номерами и в одном ряду.
Определите два соседних свободных места в одном ряду так, чтобы во всех рядах перед ними кресла с такими же номерами тоже были свободны, а ряд находился как можно дальше от сцены. Если подходящих пар в этом ряду несколько, выберите пару с наименьшими номерами мест.
Входные данные
В первой строке находятся три натуральных числа: — количество занятых мест (), — количество рядов () и — количество мест в каждом ряду (). Каждая из следующих строк содержит два натуральных числа: номер ряда (не превышает ) и номер занятого места (не превышает ).
Места, не перечисленные во входных данных, свободны. Все пары чисел различны и идут в произвольном порядке. Гарантируется, что хотя бы одна искомая пара мест в зале есть.
Выходные данные
Выведите два целых числа: сначала номер найденного ряда, затем наименьший номер места в найденной паре.
Примеры
7 7 8 1 1 6 6 5 5 6 7 4 4 2 2 3 3
5 6
3 4 5 1 3 4 1 4 2
4 4
Примечание
В первом примере подходят места 6 и 7 в ряду 5. Пара 7 и 8 тоже подходит, но начинается позже. В рядах 6 и 7 подходящей пары нет. Во втором примере выбираются места 4 и 5 в ряду 4.