문제

과학에서 단위는 어디에서나 존재한다. 물리에서 단위는 거리(미터, 키로미터 등), 무게(키로그램, 그램 등), 그리고 다른 많은 양을 측정하는데 사용한다. 컴퓨터 과학자들은 용량의 단위(키로바이트, 메가바이트, ...)를 만들어 사용하고 있다. 당신은 여러 단위들이 주어질 때 그들이 몇 배 차이나는지를 찾는 프로그램을 작성하고자 한다.

여러 단위간의 관계를 표현하는 방법은 여러가지가 존재하지만, 의미하는 바는 같다. 예를 들자면 미터계에 존재하는 단위는 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 <= N <= 10)으로 시작한다. 이어지는 줄에는 N개의 단위들이 주어진다. 각 단위는 최대 5글자이며 대소문자를 구분한다. 이어지는 N - 1개의 줄에는 서로 다른 두 단위의 관계가 주어진다. 입력 형식은 "단위의 이름" "=" "1보다 큰 정수" "왼쪽 단위보다 작은 오른쪽 단위의 이름" 순이다. 각 줄은 오른쪽의 작은 단위와 왼쪽 큰 단위가 몇 배 차이가 나는지를 설명한다. 각 단위는 N - 1줄중에 한번 이상 등장하며 주어진 입력만으로 전 단위간의 관계가 파악 가능하도록 주어진다. 단위간의 관계는 (2^31 - 1) 배보다 같거나 작은 차이가 나도록 구성되어 있다.

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

출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 단위들의 관계를 출력한다. 단위들은 왼쪽에서 오른쪽으로, 높은 단위에서 낮은 단위로 정렬되어 있어야 하며 가장 왼쪽의 단위가 1일 때 나머지 단위들은 몇인지를 "=" 기호를 통해서 나열한다.