# Problem D

Dimensional Analysis

You are deriving some equations for physics homework and are
worried you’ve made some mistakes. To debug them, you will
apply dimensional analysis. In dimensional analysis, you remove
all magnitudes and units from a set of equations until you are
left only with strings representing *physical
quantities* and the special dimensionless constant
$1$. The following is an
example set of such equations:

velocity * time = length frequency = 1 / time acceleration = velocity / time force = mass * acceleration force = mass * length / time / time

Your equations, like the ones above, involve only multiplication and division (no addition, exponentiation, etc.) As you can see, some quantities (like velocity) are defined in terms of other, more basic quantities (length, time). But you’re not sure what the correct relationships are between the quantities. You do know that none of the quantities in your equations are unitless: it should not be possible, through any set of algebraic manipulations, to prove that any quantity is equal to the dimensionless constant $1$. (You may assume that all physical quantities in your equations have positive real magnitudes. In particular, you may freely divide any equation by any quantity without worrying about division by zero; and you may take square or higher roots of any quantity.)

A set of equations violating this condition is
*invalid* (and a set of equations is valid otherwise).
The above example is a valid system. Here is an invalid
one:

foo * bar = xyzzy foo = xyzzy * bar

By substituting the second equation into the first, and
dividing both sides by `xyzzy`, you get
$\texttt{bar * bar = 1}$.
Taking a square root of both sides, you get $\texttt{bar = 1}$ and so `bar` is dimensionless.

Given the set of equations in your dimensional analysis, compute whether the equations are valid.

## Input

The first line of the input is a single integer $N$, the number of equations
$(1 \leq N \leq 100)$.
Each of the $N$ subsequent
lines of input contains one equation. An equation consists of
two expressions, separated by an equal sign surrounded by
spaces “ `=` ”. Each expression
contains one or more atoms, separated by either “ `*` ” or “ `/` ”; each
atom is either the character ‘`1`’ or a
physical quantity, represented by a lowercase string
(containing one or more ASCII characters between ‘`a`’ and ‘`z`’). At most
$100$ unique physical
quantities appear in total across all equations, each equation
contains at most $100$
atoms, and the total number of characters in all atoms across
all equations will not exceed $100\, 000$.

There will be exactly one space before and after each
‘`=`’, ‘`*`’,
and ‘`/`’ and the equations will
contain no other whitespace or other extraneous punctuation.
See the sample input for examples of how equations are
formatted.

The operator `*` represents
multiplication and `/` represents
division. Expressions follow the usual associativity rules:
`a / b * c` is the same as `a * c / b` but different from `a / b / c`.

## Output

Print `invalid` if it is possible to
prove that at least one of the physical quantities in an
equation in the input must be dimensionless. Print `valid` otherwise.

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

5 velocity * time = length frequency = 1 / time acceleration = velocity / time force = mass * acceleration force = mass * length / time / time |
valid |

Sample Input 2 | Sample Output 2 |
---|---|

2 foo * bar = xyzzy foo = xyzzy * bar |
invalid |

Sample Input 3 | Sample Output 3 |
---|---|

5 time * power = energy energy = work work = force * distance distance = distance 1 / 1 = 1 * 1 / 1 |
valid |