Впечатли своего брата, но не огорчай свою мать.
Брат и мать Робина собираются в гости, и Робин должен выбрать день приезда для каждого гостя.
Все доступные дни пронумерованы от \(1\) до \(n\). У Робина и его веселой компании запланировано всего \(k\) рискованных 'работ'. \(i\)-я работа проходит между днями \(l_i\) и \(r_i\) включительно, для \(1 \le i \le k\).
Посетители остаются на \(d\) непрерывных дней, все эти \(d\) дней должны быть между днем \(1\) и \(n\) включительно. Если работа проходит в любой из \(d\) дней, визит пересекается с работой (длина пересечения не важна).
Робин хочет, чтобы визит его брата пересекался с максимальным количеством различных работ, а визит его матери — с минимальным.
Найдите подходящие дни начала визита для брата и матери Робина. Если есть несколько подходящих дней, выберите самый ранний.
Выходные данные
Для каждого набора входных данных выведите два целых числа, лучшие дни начала визитов брата и матери Робина соответственно. Оба визита должны укладываться между днем \(1\) и \(n\) включительно.
Примечание
В первом примере единственная работа занимает все \(2\) дня, оба гостя должны приехать в день \(1\).
Во втором примере день \(2\) пересекается с \(2\) работами, а день \(1\) пересекается только с \(1\).
В третьем примере Роберт посещает дни \([1,2]\), миссис Гуд посещает дни \([4,5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|