Hide

Problem L
Sauna

Kaisa and her friends are going to the sauna!

Now they have to pick the temperature. Each of them has their own temperature preferences as an inclusive range of acceptable values. Can you help them find the temperatures that everyone is happy with?

Since there might be a large number of possible temperatures, they have asked you to just tell them how many options there are and what the lowest temperature that works for everyone is, as then the sauna will need less time to heat up.

Input

The first line of input contains an integer, $N$, the number of people in the group ($2 \le N \le 2 \cdot 10^5$). The next $N$ lines each contains two integers, $a_i$ and $b_i$, indicating that the $i$th person’s temperature preference is between $a_i$ and $b_i$, inclusive. Temperatures are given in millidegrees Celsius, with $0 \le a_i \le b_i \le 2 \cdot 10^5$.

Output

Output two integers: first, the number of different temperatures (in millidegrees Celsius) that fit all preferences; and second, the lowest such value.

If there are no values that fit all preferences, instead output “bad news”.

Explanation for sample 1

There are three possible temperatures that all three people will be happy with: 70003, 70004, 70005.

Sample Input 1 Sample Output 1
3
70000 70005
70003 70010
65000 80000
3 70003
Sample Input 2 Sample Output 2
2
70000 70500
80000 80100
bad news

Please log in to submit a solution to this problem

Log in