E. Eye Exam
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt 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.

Input

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

Each of the next $$$N$$$ lines describes a test with two integers $$$A$$$ and $$$B$$$ ($$$1 \le A \lt 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

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.

Examples
Input
1
1 31 E
Output
16 16
Input
2
1 31 A
1 31 B
Output
*
Input
3
1 5 B
1 11 A
1 5 B
Output
4 5
Input
1
3 4 E
Output
*
Note

Explanation for example 1

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

Explanation for example 2

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