Exchange Rates

Using money to pay for goods and services usually makes life easier, but sometimes people prefer to trade items directly without any money changing hands. To keep a consistent "price", traders set an exchange rate between items.

The exchange rate between two items A and B is written as two positive integers $m$ and $n$, meaning that $m$ of item A is worth $n$ of item B. For example, 2 stoves might be worth 3 refrigerators. (Mathematically 1 stove is worth 1.5 refrigerators, but since half a refrigerator is hard to come by, exchange rates are always written with integers.)

Given a list of exchange rates, write a program that computes the exchange rate between any two items.

The input consists of one or more commands, followed by a line beginning with a period (.) that marks the end of the input. Each command is on a line by itself and is either an assertion or a query.

An assertion begins with an exclamation point (!) and has the form

! m itema = n itemb

where itema and itemb are distinct item names and $m$ and $n$ are both positive integers less than 100. It states that $m$ of itema are worth $n$ of itemb.

A query begins with a question mark (?) and has the form

? itema = itemb

and asks for the exchange rate between itema and itemb. Here itema and itemb are distinct items that have both appeared in previous assertions (not necessarily the same assertion).

For each query, output the exchange rate between itema and itemb based on every assertion made up to that point. The rate must consist of integers and must be reduced to lowest terms. The output has the form

m itema = n itemb

If the exchange rate cannot be determined at that point, use question marks instead of the integers:

? itema = ? itemb

• Item names are at most 20 characters long and consist only of lowercase letters.
• Only the singular form of an item name is used (no plurals).
• There are at most 60 distinct items.
• There is at most one assertion for any pair of distinct items.
• No contradictory assertions are given. For example, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" are contradictory.
• Assertions are not necessarily in lowest terms, but the output must be.
• Although assertions use numbers less than 100, a query may produce larger numbers; when reduced to lowest terms they never exceed 10000.