Problem B
Inequality Paradox
Elizabeth hates doing homework, she will find any excuse not to do them. Her math professor, on the other hand, loves homework and tries his best to assign as much of those to his students.
For the summer break, Elizabeth’s professor assigned a very long and annoying math task to his students. He asked each of them to write a long list of inequalities, such as: $a < b$, $h > z$, and so on.
There is no way that Elizabeth will spend time on this, so she generated a bunch of random inequalities just to make her professor happy.
The problem, however, is that the professor could find out when the inequalities don’t make sense, i.e. when Elizabeth’s list contains inequalities that cause an impossible scenario (paradox).
For example, if Elizabeth generated the inequality $a < b$, then $b < c$, and then $c < a$, that would already be a paradox. The paradox could also be caused by a much more complex chain of inequalities.
Help Elizabeth find out if her list of inequalities contains is paradoxical or not!
Input
The first line contains one integer: $N$, the number of inequalities that Elizabeth has generated.
Each of the next $N$ lines contains an inequality, written in the form a x b where a and b are two different lowercase alphabetic characters, and x is either the “<” or “>” symbol.
Output
You need to write a single line containing :) if Elizabeth’s homework is not paradoxical, and :( if it is.
Constraints
-
$1 \le N \le 325$.
-
The two variables in the inequality are guaranteed to be two different lowercase alphabetic letters.
-
The inequality sign is guaranteed to be either < or <.
-
The same pair of letters will appear at most once in Elizabeth’s list, regardless of the inequality sign.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 a > b c < b a < c |
:( |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 a > f b > c a < d d < c f < b |
:) |
