Units

Time limit3sMemory limit256 MB

Summary

Given N-1 pairwise conversion relations, sort the units from largest to smallest and print the chain with the largest unit set to 1.

Level: Medium4 of 10
Topics: Graph, Sorting, Math
Solved: No attempts yet

Problem

Units show up everywhere in science. Physics measures distance (meters, kilometers), weight (kilograms, grams) and many other quantities with units, and computer scientists invented units of capacity (kilobytes, megabytes). Given several units, work out how many times larger each one is than the others.

The relations between units can be written in many ways that all mean the same thing. The metric units can be written as 1km = 1000m, 1m = 100cm, 1cm = 10mm, or as 1km = 100000cm, 1km = 1000000mm, 1m = 1000mm. Both ways lead to the same relation 1km = 1000m = 100000cm = 1000000mm.

In this problem you sort the units from largest to smallest. Among cm, km, m and mm the largest unit is km, because 1km is larger than 1cm, 1m and 1mm. Sorting the rest the same way gives km m cm mm.

Sizes always differ by an integer factor here, so a relation such as 1 inch = 2.54cm never appears. Every relation in the input says how many of a smaller unit fit in a larger unit.

Input

The input holds several test cases. Each test case starts with the number of units $N$ ( $2 \le N \le 10$ ). The next line holds $N$ unit names. Each name is at most 5 characters long and is case sensitive. The next $N - 1$ lines each describe the relation between two different units in this order: the name of the larger unit, "=", an integer greater than 1, and the name of the smaller unit. Each line says how many of the smaller unit on the right fit in the larger unit on the left. Every unit appears at least once in those $N - 1$ lines, and the given relations are enough to determine the relation between every pair of units. Any two units differ by an integer factor, and that factor is at most $2^{31} - 1$ .

A single 0 follows the last test case.

Output

For each test case print the relation between the units on one line. The units run from left to right, largest first. Set the count of the leftmost unit to 1 and list how many of each remaining unit that equals, joining the terms with " = ". In each term the count comes first and the unit name follows it with no space between them. If the largest unit is km and 1km equals 1000m, the line starts with 1km = 1000m.

If two or more units have the same size, print the one whose name comes first in ASCII order. Uppercase letters come before lowercase letters.

Examples1

Example 1

Input

4
km m mm cm
km = 1000 m
m = 100 cm
cm = 10 mm
4
m mm cm km
km = 100000 cm
km = 1000000 mm
m = 1000 mm
6
MiB Mib KiB Kib B b
B = 8 b
MiB = 1024 KiB
KiB = 1024 B
Mib = 1048576 b
Mib = 1024 Kib
6
Kib B MiB Mib KiB b
B = 8 b
MiB = 1048576 B
MiB = 1024 KiB
MiB = 8192 Kib
MiB = 8 Mib
0

Expected output

1km = 1000m = 100000cm = 1000000mm
1km = 1000m = 100000cm = 1000000mm
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b