Arbitrage?

If you are going to travel to the World Finals, you cannot rely on Czech Crowns. You would have to exchange your money for various foreign currencies. This problem deals with multiple currencies and their exchange rates. Your task is to verify that some set of exchange rates is safe, namely detect a possibility of so-called arbitrage.

An *arbitrage* is a risk-free combination of buy and
sell operations that gains profit from im- balance in market
prices. The prices may apply to various things, typically stock
exchange but also currencies.

The input consists of several test cases. Each case begins with a line containing one positive integer number $C$, $1 \leq C\leq 200$, the number of currencies.

The second line of each test case contains $C$ currency codes separated by a space. Each code is composed of 3 uppercase letters and all codes in one test case are different.

The third line contains one integer number $R, 0\leq R \leq C\cdot (C-1)$, the
number of exchange rates available. Each of the following
$R$ lines contains one
exchange rate in the following format: first currency code,
space, second currency code, space, integer number $A_ i$, colon (’`:`’), and integer number $B_ i$. The meaning is as follows: If
you pay $A_ i$ units of
the first currency, you will get $B_ i$ units of the second currency.
You may assume that $1\leq A_ i,
B_ i\leq 100$ and that the two currencies are
different.

The last test case is followed by a line with $C=0$.

For each test case, print one line of output. If there
exists any possible sequence of currency exchange operations
that would result in a profit, the line should contain the word
"`Arbitrage`". Otherwise, simply print
"`Ok`".

The word *profit* in this case means that you start
with any amount of any currency and after performing any number
of exchanges you will have strictly higher amount of the same
currency.

Sample Input 1 | Sample Output 1 |
---|---|

2 CZK EUR 2 CZK EUR 25:1 EUR CZK 1:25 2 GBP USD 2 USD GBP 8:5 GBP USD 5:9 3 BON DEM CZK 3 DEM BON 1:6 BON CZK 1:5 DEM CZK 1:20 3 CZK EUR GBP 3 CZK EUR 24:1 EUR GBP 5:4 GBP CZK 1:30 3 CZK USD GBP 4 CZK USD 28:1 CZK GBP 31:1 GBP CZK 1:31 USD GBP 1:1 0 |
Ok Arbitrage Ok Ok Arbitrage |