## Alice's Number Guessing Game

View as PDF

Points: 3
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Alice is thinking of an integer that Bob is trying to guess. Bob has asked questions of two types:

1. is for some integer ?
2. is for some integer ?

For each question, Alice responded with either yes or no. Bob remembers the questions that Alice responded yes to, but can't calculate the range that could be in!

Please help him determine the range based on Alice's responses. It may be possible that a range is impossible based on Alice's responses. If this is the case, output LIES!.

#### Input Specification

The first line will contain , the number of questions Bob has asked.

The next lines will contain space-separated integers, denoting a question Bob asked that Alice responded yes to. The first integer is either or corresponding to the question type and the second is for that question.

#### Output Specification

If a range is determined to be impossible based on Alice's responses, output LIES!.

Otherwise, output space-separated integers and , the range that could be in.

#### Sample Input 1

3
2 10
1 17
1 15

#### Sample Output 1

10 15

#### Explanation for Sample Output 1

Alice says that , , and . Based on these constraints, , so = .

#### Sample Input 2

2
1 14
2 20

#### Sample Output 2

LIES!

Alice says that and . We see that a range is impossible and Alice is lying.

#### Sample Input 3

1
1 8

#### Sample Output 3

1 8

#### Sample Input 4

4
2 4
2 3
2 5
2 8

#### Sample Output 4

8 1000000000