Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели N
различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями A и B
происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени. Помогите ему!
Входные данные
В первой строке вводится число N – количество цивилизаций, культура которых интересует Петю (1≤N≤100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа S
i и E
i
– год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 10
9
по абсолютной величине, S
i < E
i.
Выходные данные
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-600 -400
-450 -300
-400 -50
|
1 2
|
|
2
|
2
10 20
15 21
|
1 2
|
|
3
|
1
77777 77778
|
0
|