你正在推导一些物理作业的方程，并担心自己犯了一些错误。为了调试这些方程，你将应用量纲分析。在量纲分析中，你从一组方程中移除所有的量级和单位，只留下代表物理量和特殊无量纲常数 1 的字符串。以下是一组此类方程的示例：

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

你的方程（如上所示）仅涉及乘法和除法（没有加法、幂运算等）。正如你所见，一些量（如速度）是根据其他更基本的量（长度、时间）定义的。但你不确定这些量之间的正确关系是什么。你知道方程中的任何量都不应该是无量纲的：通过任何代数运算，都不应该能够证明任何量等于无量纲常数 1。（你可以假设方程中的所有物理量都具有正实数量级。特别地，你可以自由地用任何量除以方程，而不必担心除以零；你也可以对任何量进行平方或更高次开方。）

违反此条件的方程组是 invalid（否则该方程组是 valid）。上面的示例是一个有效的系统。下面是一个无效的系统：

foo * bar = xyzzy
foo = xyzzy * bar

通过将第二个方程代入第一个方程，并将等式两边同时除以 xyzzy，得到 bar * bar = 1。对两边开平方，得到 bar = 1，因此 bar 是无量纲的。

给定你的量纲分析中的方程组，计算这些方程是否有效。

输入格式

输入的第一行是一个整数 $N$，表示方程的数量 ($1 \le N \le 100$)。接下来的 $N$ 行，每行包含一个方程。一个方程由两个表达式组成，中间由用空格隔开的等号 “ = ” 分隔。每个表达式包含一个或多个原子，由 “ * ” 或 “ / ” 分隔；每个原子要么是字符 ‘1’，要么是一个物理量，由小写字符串（包含一个或多个 ‘a’ 到 ‘z’ 之间的 ASCII 字符）表示。所有方程中总共最多出现 100 个不同的物理量，每个方程最多包含 100 个原子，所有方程中所有原子的字符总数不超过 100 000。

每个 ‘=’、‘*’ 和 ‘/’ 前后各有一个空格，方程中不包含其他空格或其他无关的标点符号。请参阅样例输入以了解方程的格式。

运算符 * 表示乘法，/ 表示除法。表达式遵循通常的结合律规则：a / b * c 与 a * c / b 相同，但与 a / b / c 不同。

输出格式

如果可以证明输入方程中的至少一个物理量必须是无量纲的，则输出 invalid。否则，输出 valid。

样例

样例输入 1

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

样例输出 1

valid

样例输入 2

2
foo * bar = xyzzy
foo = xyzzy * bar

样例输出 2

invalid

样例输入 3

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

样例输出 3

valid