k = int(input())
letters = input().split(" ")
letter_to_int = {}
for i in range(k):
    letter_to_int[letters[i]] = i

assembly = [[[0,0] for _ in range(k)] for _ in range(k)]


for i in range(k):
    line = input().split(" ")
    for j in range(k):
        cost,c = line[j].split('-')
        cost = int(cost)
        assembly[i][j] = [cost,c]

cp_producing = [[] for _ in range(k)]
for i in range(k):
    for j in range(k):
        cost,c = assembly[i][j]
        cp_producing[c].append((i,j))
        

def solve(w):
    n = len(w)
    # dp[i][j][c] is optimal w_i..j becoming c
    dp = [ [ [float("inf") for _ in range(k)] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i][letter_to_int[w[i]]] = 0
    for l in range(1,n):
        for i in range(n-l):
            j = i + l
            for h in range(i,j):
                for c1 in range(k):
                    for c2 in range(k):
                        cost,c = assembly[c1][c2]
                        c = letter_to_int[c]
                        dp[i][j][c] = min(dp[i][j][c], dp[i][h][c1] + dp[h+1][j][c2] + cost)
    best_c = 0
    best = float("inf")
    for c in range(k):
        if dp[0][n-1][c] < best:
            best_c = c
            best = dp[0][n-1][c]
    print(best,end="")
    print("-",end="")
    print(letters[best_c])

n = int(input())
for _ in range(n):
    w = input()
    solve(w)

_ = input()