Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

D. Роберт Гуд и миссис Гуд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Впечатли своего брата, но не огорчай свою мать.

Брат и мать Робина собираются в гости, и Робин должен выбрать день приезда для каждого гостя.

Все доступные дни пронумерованы от $$$1$$$ до $$$n$$$. У Робина и его веселой компании запланировано всего $$$k$$$ рискованных 'работ'. $$$i$$$-я работа проходит между днями $$$l_i$$$ и $$$r_i$$$ включительно, для $$$1 \le i \le k$$$.

Посетители остаются на $$$d$$$ непрерывных дней, все эти $$$d$$$ дней должны быть между днем $$$1$$$ и $$$n$$$ включительно. Если работа проходит в любой из $$$d$$$ дней, визит пересекается с работой (длина пересечения не важна).

Робин хочет, чтобы визит его брата пересекался с максимальным количеством различных работ, а визит его матери — с минимальным.

Найдите подходящие дни начала визита для брата и матери Робина. Если есть несколько подходящих дней, выберите самый ранний.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$d$$$, $$$k$$$ ($$$1 \le n \le 10^5, 1 \le d, k \le n$$$) — количество дней, продолжительность визитов и количество работ.

Затем следуют $$$k$$$ строк, каждая содержит по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — начальный и конечный день каждой работы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите два целых числа, лучшие дни начала визитов брата и матери Робина соответственно. Оба визита должны укладываться между днем $$$1$$$ и $$$n$$$ включительно.

Пример
Входные данные
6
2 1 1
1 2
4 1 2
1 2
2 4
7 2 3
1 2
1 3
6 7
5 1 2
1 2
3 5
9 2 1
2 8
9 2 4
7 9
4 8
1 3
2 3
Выходные данные
1 1
2 1
1 4
1 1
1 1
3 4
Примечание

В первом примере единственная работа занимает все $$$2$$$ дня, оба гостя должны приехать в день $$$1$$$.

Во втором примере день $$$2$$$ пересекается с $$$2$$$ работами, а день $$$1$$$ пересекается только с $$$1$$$.

В третьем примере Роберт посещает дни $$$[1,2]$$$, миссис Гуд посещает дни $$$[4,5]$$$.