생산 공정

현종이는 공장 노동자이다. 부푼 꿈을 안고 입사해 20년간 일해 왔으나, 이번 달에 생산 효율이 오르지 않으면 다음 달에 해고될 것이라는 청천벽력 같은 소식을 듣고 말았다. 현종이의 일은 간단하다. 주어진 순서대로 조각을 조립하여 제품을 만들면 된다. 그런데 조각 a, b, c를 조립할 때, a-b를 먼저 조립한 뒤 c를 이어 붙이는 것과 b-c를 먼저 조립한 뒤 a를 이어 붙이는 데 걸리는 시간이 서로 다르다. 현종이는 이 공정을 효율적으로 개선하면 공장 일을 계속할 수 있으리라 판단했다.

현종이를 돕기 위해, 당신은 모든 조각을 조립하는 가장 좋은 방법을 알려 주는 프로그램을 작성하면 된다. 먼저 조각의 목록이 주어지고, 그다음 줄부터는 두 조각을 이어 붙이는 데 걸리는 시간과 그 결과물이 표 형태로 주어진다.

예를 들어 보자. 조각 a와 a를 이어 붙이는 데에는 3의 시간이 걸리고 그 결과는 부품 b가 되며, 이 결과물의 뒤에 다시 a를 이어 붙이는 데에는 6의 시간이 걸린다고 하자. 표는 대칭이 아닐 수 있다. 즉, b-a를 조립하는 시간과 a-b를 조립하는 시간이 다를 수 있다.

만들고자 하는 완성품이 aba라면, 가능한 두 가지 조립 순서는 다음과 같다.

• (ab)a = ba = a, time = time(ab) + time(ba) = 5 + 6 = 11
• a(ba) = aa = b, time = time(ba) + time(aa) = 6 + 3 = 9

따라서 출력은 9-b가 된다.

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫 줄에는 자연수 $k$($1 \le k \le 26$)가 주어지고, 그다음 줄에는 조각의 이름들이 공백으로 구분되어 주어진다(각 이름은 $[a\text{-}z]$에 속하는 알파벳 한 글자).

그다음 $k$개의 줄에는 생산 공정 표가 주어진다. 각 줄은 $k$개의 문자열로 이루어지며, $i$행 $j$열의 값은 $i$번째 부품(왼쪽)과 $j$번째 부품(오른쪽)을 조립하는 데 걸리는 시간과 그 결과물을 time-result 형태로 나타낸다. 조립에 걸리는 시간은 $0$ 이상 $1000000$ 이하의 정수이며, 결과물로 잘못된 문자가 주어지는 경우는 없다.

그다음 줄에는 만들고자 하는 완성품의 개수 $n$이 주어지고, 이어지는 $n$개의 줄에 완성품의 형태가 주어진다. 각 완성품은 $200$개 이하의 부품으로 이루어지며, 주어진 형태를 바꾸어 조립할 수는 없다.

$k = 0$이면 프로그램을 종료하며, 이 경우에는 아무것도 출력하지 않는다.

각 테스트 케이스에 대해, 각 완성품을 가장 빨리 만들 수 있을 때 걸리는 시간과 그때의 결과물을 time-result 형태로 한 줄에 하나씩 출력한다. 만일 그러한 경우가 여러 가지이면서 결과물이 서로 다르다면, 처음 주어진 부품 목록에서 더 먼저 등장하는 결과물을 출력한다. 예를 들어 결과로 5-b와 5-c가 모두 가능하고 테스트 케이스의 둘째 줄에서 입력받은 부품 목록이 a c b였다면 5-c를 출력하면 된다.

연속한 테스트 케이스 사이에는 빈 줄을 하나 출력한다.