단위

과학에서 단위는 어디에나 있다. 물리에서는 거리(미터, 킬로미터)나 무게(킬로그램, 그램)를 비롯한 여러 양을 재는 데 단위를 쓰고, 컴퓨터 과학에서는 용량 단위(킬로바이트, 메가바이트)를 만들어 쓴다. 여러 단위가 주어졌을 때 서로 몇 배 차이가 나는지 구하는 프로그램을 작성한다.

단위 사이의 관계를 적는 방법은 여러 가지지만 뜻하는 바는 같다. 미터계 단위는 1km = 1000m, 1m = 100cm, 1cm = 10mm로 적을 수도 있고 1km = 100000cm, 1km = 1000000mm, 1m = 1000mm로 적을 수도 있다. 두 표기 모두에서 1km = 1000m = 100000cm = 1000000mm라는 같은 관계를 이끌어낼 수 있다.

이 문제에서는 단위를 큰 것부터 작은 것 순으로 정렬한다. cm, km, m, mm 가운데 가장 큰 단위는 km이다. 1km이 1cm, 1m, 1mm보다 크기 때문이다. 나머지 단위도 같은 방법으로 정렬하면 km m cm mm 순이 된다.

단위 사이의 크기 차이는 언제나 정수배다. 그래서 1인치 = 2.54cm 같은 관계는 생각하지 않아도 된다. 입력의 관계는 항상 큰 단위가 작은 단위의 몇 배인지로 주어진다.

여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 단위의 가짓수 $N$($2 \le N \le 10$)이 주어진다. 다음 줄에는 $N$개의 단위 이름이 주어진다. 각 이름은 최대 5글자이고 대소문자를 구분한다. 이어지는 $N - 1$개의 줄에는 서로 다른 두 단위의 관계가 "큰 단위의 이름", "=", "1보다 큰 정수", "작은 단위의 이름" 순서로 주어진다. 각 줄은 왼쪽의 큰 단위가 오른쪽의 작은 단위의 몇 배인지를 뜻한다. 각 단위는 그 $N - 1$개의 줄에 한 번 이상 나오고, 주어진 관계만으로 모든 단위 사이의 관계를 알아낼 수 있다. 어떤 두 단위든 크기 차이는 정수배이며 $2^{31} - 1$배 이하다.

모든 입력이 끝나면 0이 주어진다.

각 테스트 케이스마다 단위 사이의 관계를 한 줄에 출력한다. 단위는 왼쪽에서 오른쪽으로 큰 것부터 작은 것 순으로 놓는다. 가장 왼쪽 단위의 개수를 1로 두고 나머지 단위가 각각 몇 개인지를 " = "로 이어 붙인다. 각 항은 개수를 먼저 쓰고 공백 없이 단위 이름을 붙여 쓴다. 가장 큰 단위가 km이고 1km이 1000m과 같다면 그 줄은 1km = 1000m으로 시작한다.

크기가 같은 단위가 둘 이상이면 이름의 아스키 코드 순서가 앞서는 단위를 먼저 적는다. 대문자가 소문자보다 앞선다.