Sauna

Interview

Time limit1.5sMemory limit1024 MB

Summary

Find how many temperatures lie in every person's inclusive range and the lowest such temperature, or report bad news if none exist.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

Kaisa and her friends are going to the sauna. Each of them has a temperature preference given as an inclusive range. Help them find the temperatures that everyone is happy with.

There may be many possible temperatures, so they only want to know how many options there are and the lowest temperature that works for everyone. The sauna needs less time to heat up at the lowest temperature.

Input

The first line contains an integer $N$ , the number of people ( $2 \le N \le 2 \cdot 10^5$ ). Each of the next $N$ lines contains two integers $a_i$ and $b_i$ , meaning the $i$ -th person accepts temperatures from $a_i$ to $b_i$ , inclusive. Temperatures are in millidegrees Celsius, with $0 \le a_i \le b_i \le 2 \cdot 10^5$ .

Output

Print two integers: the number of temperatures (in millidegrees Celsius) that fit every preference, and the lowest such temperature. If no temperature fits every preference, print "bad news".

Examples2

Example 1

Input

3
70000 70005
70003 70010
65000 80000

Expected output

3 70003

Example 2
Input
```
2
70000 70500
80000 80100
```
Expected output
```
bad news
```