차원 해석

물리 숙제를 하면서 방정식을 유도하던 중 실수를 했을까 걱정이 된다. 이를 디버깅하기 위해 차원 해석을 적용하려 한다. 차원 해석에서는 방정식들에서 모든 크기와 단위를 제거하여 물리량을 나타내는 문자열과 무차원 상수 $1$만 남긴다. 다음은 그러한 방정식들의 예시이다:

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

위의 방정식들처럼, 여러분의 방정식들도 곱셈과 나눗셈만 포함한다(덧셈, 거듭제곱 등은 없다). 보다시피 어떤 물리량들(예: velocity)은 다른 더 기본적인 물리량들(length, time)로 정의된다. 하지만 물리량들 사이의 올바른 관계가 무엇인지는 확실하지 않다. 다만 여러분의 방정식에 있는 어떤 물리량도 무차원이 아니라는 것은 알고 있다: 어떤 대수적 조작을 통해서도 어떤 물리량이 무차원 상수 $1$과 같다는 것을 증명할 수 없어야 한다. (여러분의 방정식에 있는 모든 물리량은 양의 실수 크기를 가진다고 가정해도 된다. 특히 0으로 나누는 것을 걱정하지 않고 어떤 방정식이든 어떤 물리량으로든 자유롭게 나눌 수 있으며, 어떤 물리량의 제곱근이나 더 높은 차수의 근을 취할 수도 있다.)

이 조건을 위반하는 방정식 집합은 invalid이다(그렇지 않은 방정식 집합은 valid이다). 위의 예시는 valid한 시스템이다. 다음은 invalid한 예시이다:

foo * bar = xyzzy
foo = xyzzy * bar

두 번째 방정식을 첫 번째 방정식에 대입하고 양변을 xyzzy로 나누면 bar * bar = 1을 얻는다. 양변의 제곱근을 취하면 bar = 1이므로 bar는 무차원이다.

차원 해석의 방정식 집합이 주어졌을 때, 그 방정식들이 valid한지 계산하라.

입력의 첫 번째 줄은 정수 $N$이며, 이는 방정식의 개수이다($1 ≤ N ≤ 100$). 이후 $N$개의 줄 각각에는 방정식 하나가 들어 있다. 방정식은 두 표현식으로 이루어지며, 공백으로 둘러싸인 등호 “ = ”로 구분된다. 각 표현식은 하나 이상의 원자로 이루어지며, 원자들은 “ * ” 또는 “ / ”로 구분된다. 각 원자는 문자 ‘1’이거나 물리량이며, 물리량은 소문자 문자열(‘a’부터 ‘z’까지의 ASCII 문자 하나 이상으로 구성됨)로 표현된다. 모든 방정식에 걸쳐 총 $100$개 이하의 서로 다른 물리량이 나타나고, 각 방정식은 $100$개 이하의 원자를 포함하며, 모든 방정식의 모든 원자에 있는 총 문자 수는 $100\,000$을 넘지 않는다.

각 ‘=’, ‘*’, ‘/’ 앞뒤에는 정확히 하나의 공백이 있고, 방정식에는 그 외의 공백이나 다른 불필요한 문장 부호가 없다. 방정식이 어떻게 형식화되는지에 대한 예는 샘플 입력을 참조하라.

연산자 *는 곱셈을, /는 나눗셈을 나타낸다. 표현식은 일반적인 결합 규칙을 따른다: a / b * c는 a * c / b와 같지만 a / b / c와는 다르다.

입력에 있는 방정식의 물리량 중 적어도 하나가 무차원이어야 함을 증명할 수 있으면 invalid를 출력한다. 그렇지 않으면 valid를 출력한다.