На подводной исследовательской станции «Нептун-7» требуется установить новый научный модуль. Станция состоит из M уровней (пронумерованных от 1 до M сверху вниз, где уровень 1 ближе всего к поверхности) и K отсеков на каждом уровне.
Некоторые отсеки уже заняты оборудованием. По требованиям безопасности, новый модуль нужно разместить так, чтобы над ним (на уровнях с меньшими номерами) было как можно больше подряд идущих свободных отсеков с тем же номером — это обеспечивает путь аварийной эвакуации к поверхности.
Если несколько отсеков имеют одинаковое максимальное количество свободных отсеков над ними, выбирается отсек на уровне ближе к поверхности (с меньшим номером уровня).
Гарантируется, что хотя бы один свободный отсек на станции существует.
Формат входных данных
В первой строке находятся три числа:
- N — количество занятых отсеков (1 ≤ N ≤ 10 000)
- M — количество уровней (1 ≤ M ≤ 100 000)
- K — количество отсеков на каждом уровне (1 ≤ K ≤ 100 000)
В следующих N строках находятся пары натуральных чисел: номер уровня и номер отсека занятого места соответственно.
Формат выходных данных
Два целых числа через пробел:
- Номер уровня выбранного отсека
- Количество свободных отсеков над ним (подряд, с тем же номером)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 6 7
1 1
2 4
3 6
6 1
4 3
5 5
5 2
6 6
4 7
|
4 3
|