은하계 수입

새로 개발된 ThrustoZoom 초차원 드라이브 덕분에, 뉴저지의 수출입 대기업 HyperCommodities는 우주에서 가장 먼 은하계와도 교역할 수 있게 되었습니다. HyperCommodities는 Plural Z 구역에 있는 몇몇 은하계에서 상품을 수입하려고 합니다. 이 은하계의 행성들은 진공 밀봉재, 투명 알루미늄, 다이그래파이트, 퀀텀 강철 같은 귀중한 제품과 원자재를 수출합니다. 예비 조사로 다음 사실이 밝혀졌습니다.

• 각 은하계에는 행성이 최소 1개, 최대 26개 있습니다. 은하계 안의 각 행성은 A부터 Z까지의 서로 다른 알파벳 한 글자로 식별됩니다.
• 각 행성은 한 가지 상품의 생산과 수출에 특화되어 있습니다. 같은 은하계 안의 서로 다른 행성은 서로 다른 상품을 수출합니다.
• 일부 행성 쌍은 초공간 운송 노선으로 연결되어 있습니다. 행성 A와 B가 연결되어 있으면 두 행성은 자유롭게 교역할 수 있습니다. 행성 C가 B와는 연결되어 있지만 A와는 연결되어 있지 않다면, A와 C는 여전히 B를 거쳐 교역할 수 있으나 이때 B가 운송료로 배송량의 5%를 가져갑니다. (따라서 A는 C가 보낸 양의 95%만 받고, C도 A가 보낸 양의 95%만 받습니다.) 일반적으로 두 행성은 운송 노선들로 연결되어 있기만 하면 교역할 수 있으며, 운송 경로 위의 각 중간 행성은 자신이 운송하는 양의 5%를 가져갑니다(이는 원래 배송량의 5%와 반드시 같지는 않습니다).
• 각 은하계의 적어도 한 행성은 지구로 향하는 ThrustoZoom 노선을 개설할 의향이 있습니다. ThrustoZoom 노선은 사업적으로 볼 때 은하계 안의 다른 운송 노선과 동일합니다. 예를 들어 행성 K가 지구로 ThrustoZoom 노선을 개설하면, 지구는 K와 자유롭게 교역할 수 있고, K와 연결된 임의의 행성과도 통상적인 운송료를 물며 교역할 수 있습니다.

HyperCommodities는 각 행성의 주력 수출품에 상대 가치(10보다 작은 양의 실수)를 부여했습니다. 값이 클수록 제품이 더 가치 있으며, 더 가치 있는 제품은 국내 시장에서 더 높은 마진으로 되팔 수 있습니다. 문제는 운송료를 고려했을 때 어느 행성의 수출품이 가장 가치 있는지 알아내는 것입니다.

입력은 하나 이상의 은하계 설명으로 이루어집니다. 각 은하계 설명은 그 은하계의 행성 수를 나타내는 정수 $N$이 적힌 줄로 시작합니다. 이어지는 $N$개의 줄에는 각 행성의 설명이 들어 있으며, 각 줄은 다음으로 구성됩니다.

1. 행성을 나타내는 알파벳.
2. 공백.
3. d.dd 형식으로 표기된 그 행성 수출품의 상대 가치.
4. 공백.
5. 알파벳과 * 문자로 이루어진 문자열. 알파벳은 해당 행성으로의 운송 노선을 뜻하고, *는 지구로 ThrustoZoom 노선을 개설할 의향이 있음을 뜻합니다.

입력은 파일 끝(EOF)에서 종료됩니다.

각 은하계 설명에 대해, 운송료를 고려했을 때 수출품이 가장 가치 있는 행성 $P$의 알파벳을 사용하여 Import from P라고 적힌 한 줄을 출력합니다. 가장 가치 있는 수출품 값을 가진 행성이 둘 이상이면 알파벳 순으로 가장 앞선 행성을 출력합니다.