돈을 보여줘

Frank Marks는 큰 회사의 사무실에서 일한다. 이 회사의 고객들은 세계 곳곳에 있어 여러 종류의 통화를 다뤄야 한다. 직원들은 100 미국 달러나 452 유로처럼 특정 금액을 요청하는 청구서를 들고 사무실을 찾아온다. Frank에게 요청받은 통화가 충분히 있으면 정확히 그만큼을 내주고, 부족하면 다른 통화로 대신 지급한다.

요청받은 통화가 완전히 바닥났을 때 Frank는 대체 통화를 골라야 한다. 알려진 환율을 통해 요청 통화와 가치를 연결할 수 있는 통화라면 무엇이든 고를 수 있으며, 반드시 요청한 가치 이상을 지급해야 한다(요청 가치보다 모자라면 안 된다). 그런 대체 통화들 중에서, 요청한 가치보다 모자라지 않으면서(즉 그 이상을 지급하면서) 그 가치에 가능한 한 가까운 것을 고르고자 한다.

예를 들어 Frank가 여섯 통화 A, B, C, D, E, F 사이의 다음 환율을 알고 있다고 하자.

23 A = 17 B
16 C = 29 E
5 B = 14 E
1 D = 7 F

환율 v1 name1 = v2 name2는 name1 v1단위가 name2 v2단위와 정확히 같은 가치를 가진다는 뜻이다. 100 A를 요청하는 청구서가 들어왔지만 Frank에게 A가 하나도 없다고 하자. 그는 74 B(약 100.12 A에 해당), 115 C(약 100.72 A에 해당), 또는 207 E(약 100.02 A에 해당)를 내줄 수 있으며, 이 중 모자라지 않으면서 가장 가까운 것은 207 E이다. 주어진 환율만으로는 A를 D나 F와 연결할 방법이 없으므로, A로 표시된 요청을 만족시키는 데 그 통화들은 쓸 수 없다.

또한 Frank는 어떤 통화든 최대 100,000단위까지만 보유하고 있으므로, 대체 통화는 필요한 단위 수가 100,000 이하일 때에만 사용할 수 있다. 예를 들어 64,000 A 요청은 E로는 맞출 수 없고(100,000단위를 넘게 필요로 하므로) 대신 73,078 C로 맞춰야 한다.

환율과 청구서가 주어질 때, Frank에게 요청 통화는 하나도 없고 다른 모든 통화는 충분히 있다고 가정하여, 가장 적절한 대체 통화와 그 단위 수를 구하여라.

입력에는 여러 개의 테스트 케이스가 들어 있다. 각 테스트 케이스는 환율의 개수를 나타내는 양의 정수 n이 적힌 줄로 시작한다. 이어지는 n개의 줄은 다음 형식이다.

val1 name1 = val2 name2

여기서 name1과 name2는 서로 다른 두 통화의 이름이고, val1과 val2는 두 통화 사이의 비율을 나타내는 30 이하의 양의 정수이다(name1 v1단위가 name2 v2단위와 같은 가치를 가진다). 서로 다른 통화 이름은 최대 8개이며, 임의의 두 통화 쌍은 최대 한 번만 나열된다. 통화 이름은 최대 10개의 알파벳 문자로 이루어진다. 입력에는 모순이 없다(예컨대 1 A = 2 B, 1 B = 2 C, 1 C = 2 A가 동시에 성립하는 일은 없다).

n개의 환율 줄 다음에는 다음 형식의 줄이 하나 온다.

val name

이 줄은 요청 금액(100,000 이하의 양의 정수)과 요청 통화의 이름을 나타낸다.

마지막 테스트 케이스 뒤에는 0 하나만 있는 줄이 온다.

각 테스트 케이스에 대해 Case X: units name 형식의 줄을 출력한다. 여기서 X는 테스트 케이스 번호(1부터 시작)이고, units name은 대체 통화와 그 단위 수로, 요청 통화는 하나도 없고 다른 모든 통화는 충분하다고 가정할 때 요청한 가치보다 모자라지 않으면서(그 이상이면서) 그 가치에 가장 가까운 값을 준다. 각 테스트 케이스의 답은 유일하다.