Задача 4 из 21

Места с открытым обзором

Время 2 с · память 256 МБ

При покупке билетов на концерт известно, какие места в зале уже заняты. В зале MM рядов по KK мест в каждом; ряды нумеруются от сцены, нумерация рядов и мест ведётся с единицы. Соседними считаются места с номерами kk и k+1k+1 в одном ряду.

Определите два соседних свободных места в одном ряду так, чтобы во всех рядах перед ними кресла с такими же номерами тоже были свободны, а ряд находился как можно дальше от сцены. Если подходящих пар в этом ряду несколько, выберите пару с наименьшими номерами мест.

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

В первой строке находятся три натуральных числа: NN — количество занятых мест (N≤10 000N \le 10\,000), MM — количество рядов (M≤100 000M \le 100\,000) и KK — количество мест в каждом ряду (2≤K≤100 0002 \le K \le 100\,000). Каждая из следующих NN строк содержит два натуральных числа: номер ряда (не превышает MM) и номер занятого места (не превышает KK).

Места, не перечисленные во входных данных, свободны. Все пары чисел различны и идут в произвольном порядке. Гарантируется, что хотя бы одна искомая пара мест в зале есть.

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

Выведите два целых числа: сначала номер найденного ряда, затем наименьший номер места в найденной паре.

Примеры

Ввод 1
7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3
Вывод 1
5 6
Ввод 2
3 4 5
1 3
4 1
4 2
Вывод 2
4 4

Примечание

В первом примере подходят места 6 и 7 в ряду 5. Пара 7 и 8 тоже подходит, но начинается позже. В рядах 6 и 7 подходящей пары нет. Во втором примере выбираются места 4 и 5 в ряду 4.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче