题目描述

During the warmup session of Programadores de América (PDA) in Santiago de Chile, Ezequiel notices something alarming: the scoreboard looks blurry. Worried that the same thing might happen during the actual contest, he decides to quickly take an eye exam.

The optometrist runs a series of tests to find Ezequiel’s true prescription, which is an integer $x$. Unfortunately, instead of carefully narrowing down the prescription, the optometrist uses the lenses in no particular order. Thus, in each test Ezequiel is shown two lenses with different correction degrees $A$ and $B$ ($A < B$), and he must tell his opinion about which lens is better. For each test Ezequiel answers:

• “A” if he thinks that $A$ is strictly closer to $x$ than $B$.
• “B” if he thinks that $B$ is strictly closer to $x$ than $A$.
• “E” if he thinks that $A$ and $B$ are equally close to $x$.

After running the tests in such a strange way, the optometrist does not know what to do with Ezequiel’s answers, so they need your help. Given the results of all tests, you must determine the minimum and maximum integer prescriptions that are consistent with the tests. If no integer prescription is consistent with the tests, you must report it.

输入格式

The first line contains an integer $N$ ($1 \le N \le 1000$) indicating the number of tests.

Each of the next $N$ lines describes a test with two integers $A$ and $B$ ($1 \le A < B \le 1000$), followed by an uppercase letter $C$ (either “A”, “B” or “E”), where $A$ and $B$ are the correction degrees of the lenses and $C$ is Ezequiel’s answer.

It is guaranteed that there is a finite number of integer prescriptions that are consistent with the tests.

输出格式

Output a single line with the character “*” (asterisk) if no integer prescription is consistent with the tests. Otherwise, output a single line with two integers indicating the minimum and maximum prescriptions that are consistent with the tests.

1
1 31 E

16 16

2
1 31 A
1 31 B

*

3
1 5 B
1 11 A
1 5 B

4 5

1
3 4 E

*

提示

Explanation of Sample 1:

The only integer prescription that is equally close to $1$ and $31$ is $16$.

Explanation of Sample 2:

No integer prescription is consistent with the tests, because it should be strictly closer to both $1$ and $31$.