Ancient Civilizations
Petya has recently developed an interest in ancient civilizations. He discovered the birth and demise dates of N different ancient civilizations in an encyclopedia and is now curious about the cultural influences these civilizations had on each other.
Petya assumes that there was a cultural exchange between two civilizations, A and B, if they coexisted for any non-zero period. For instance, if civilization A began in 600 BC and lasted until 400 BC, and civilization B started in 450 BC and ended in 300 BC, then they influenced each other culturally for 50 years. Conversely, if civilization C started in 400 BC and lasted until 50 BC, it could not have exchanged culture with civilization A, but it did with civilization B for 100 years.
To advance his research, Petya wants to identify the pair of civilizations that had the shortest non-zero period of cultural exchange. Can you help him?
Input
The first line of the input contains the integer N, representing the number of civilizations Petya is interested in (1 ≤ N ≤ 100000). The following N lines each describe a civilization with two integers, S_i and E_i, indicating the year of emergence and the year of demise, respectively. All numbers are within the absolute value of 10^9, and S_i < E_i.
Output
Output two integers, representing the indices of the civilizations whose periods of existence have the smallest non-zero overlap. If no two civilizations overlap in time, output the single number 0.