Fruit Weights

Time limit1sMemory limit128 MB

Summary

Given inequalities between multiples of unknown fruit weights, decide if the query, its reverse, both, or neither must hold, or the givens contradict.

Level: Medium7 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

Compare fruits by weight. In this problem every fruit of the same kind is identical and weighs the same, and every weight is positive.

One comparison is written as $a X \le b Y$ , where $a$ and $b$ are positive integers and $X$ and $Y$ are fruit names. It says that $a$ fruits of type $X$ weigh no more than $b$ fruits of type $Y$ .

Given several such comparisons, decide the result of one more comparison.

Input

The input holds several test cases. The first line of each test case has $n$ , the number of given comparisons. Each of the next $n$ lines has one comparison in the form a X b Y, which means $a X \le b Y$ . The last line of the test case has a query in the same form a X b Y, and you compare $a X$ with $b Y$ .

A line with $n = 0$ marks the end of the input and is not processed. Apart from that final $n = 0$ , every integer in the input is positive and at most 100. Fruit names are case sensitive strings of lowercase and uppercase letters with length at most 50.

Output

Print one line per test case. For a query a X b Y the result is one of the following.

<=: you are sure that $a X \le b Y$ .
>=: you are sure that $a X \ge b Y$ .
==: you are sure that $a X = b Y$ , that is, you reached both of the two results above.
UNAVAILABLE: you can say nothing for sure about $a X$ and $b Y$ , that is, you reached none of the three results above.
INCONSISTENT: the given comparisons contradict one another, that is, you are sure they cannot all hold at the same time.

When the comparisons contradict one another, print INCONSISTENT rather than any other result.

Examples1

Example 1

Input

2
2 Orange 3 Apple
1 Apple 1 Peach
2 Orange 3 Peach
1
2 Orange 3 Apple
2 Orange 2 Apple
2
3 a 2 A
2 A 3 a
5 A 5 a
2
3 B 2 A
2 A 3 B
2 A 3 B
3
2 b 2 A
2 A 2 C
3 C 2 b
1 A 1 b
0

Expected output

<=
UNAVAILABLE
>=
==
INCONSISTENT