Assembly line#1826

Assembly line

10 seconds

256 megabytes

Very easy

The last worker in a production line at the factory of Automated Composed Machinery is worried. She knows that her job hangs in the balance unless her productivity increases. Her work consists of assembling a set of pieces in a given sequence, but the time spent assembling pieces $a$ and $b$ , then $c$ , may not be the same as assembling $b$ and $c$ and then $a$ with the resulting component. Only two consecutive pieces can be assembled at a time, and once assembled they behave as another piece in terms of the time needed for further assembly.

To aid her, you need to find the optimal way to assemble all components. The input to your program will be a set of symbols representing types of pieces, and an assembly table indicating the time it takes to assemble them, as well as the type of the resulting component. For instance, we may have two symbols ${a, b}$ and the following table:

This means, for example, that two pieces of type $a$ and $a$ may be assembled in $3$ minutes, and the result is a component of type $b$ , so that the time required to assemble it again with another piece of, say, type $a$ is $6$ minutes, and so on. Note that the table is not symmetric, i.e., assembling $b$ and $a$ may be more time-consuming than $a$ and $b$ .

For a sequence of components labeled $aba$ , the two possible solutions are:

$(ab) a = ba = a$ (ab)a = ba = a with time $time (ab) + time (ba) = 5 + 6 = 11$ \text{time}(ab) + \text{time}(ba) = 5 + 6 = 11.
$a (ba) = aa = b$ a(ba) = aa = b with time $time (ba) + time (aa) = 6 + 3 = 9$ \text{time}(ba) + \text{time}(aa) = 6 + 3 = 9.

So the result for this case would be a piece of type $b$ in $9$ minutes (denoted $9 - b$ ).

Input

The input consists of several test cases. Each test case begins with a line containing a natural number $k$ ( $1 \leq k \leq 26$ 1 \leq k \leq 26), followed by a line with $k$ symbols (characters in $[a - z]$ [a-z]) separated by spaces. The following $k$ lines contain the assembly table: the $i$ -th line has $k$ pairs of the form $time - result$ , where $time$ is an integer between $0$ and $1000000$ inclusive, and $result$ is a symbol belonging to the preceding set. The $j$ -th pair in the $i$ -th line represents the time to compose pieces of the types represented by the $i$ -th and $j$ -th symbols, and the type of the resulting piece. After the table, a line with an integer $n$ indicates the number of lines that follow, each line being a string of at most $200$ symbols. Each of these lines is a sequence of components that must be assembled together in the right order.

The input will finish with a line containing $^{'} 0^{'}$ '0', which should not be processed.

Output

For each test case, print $n$ lines, each with an integer time and a symbol result in the format $time - result$ . Each line represents the minimum time and the type of the resulting piece for the corresponding case in the input. In case of a tie among several possible results with the same minimum time, choose the piece whose type letter appears first in the line containing the $k$ symbols at the beginning of the test case. (For example, if that line was $a c b$ and both $c$ and $b$ can be obtained with minimum cost $5$ , print $5 - c$ ).

There must be an empty line between the outputs of different test cases.

Examples

Example 1