Message

When little Sascha grew up, she lost the habit of pronouncing words in whatever way was easiest for her instead of the way they are correctly pronounced. She never lost her linguistic creativity, though. When the Earth Allied Forces (EAF) discovered that she also had brilliant mathematical insight and a talent for puzzles and secret messages, she was immediately made Head of the EAF Intelligence Department.

Sascha's current task is to interpret intercepted internal messages of the hostile Mars Federation. Although every Martian message consists of just a single word, the job is hard, because two factors shape the message that is actually intercepted:

• The extraterrestrial environment is so harsh that transmission errors occur. An error replaces a character with another character of the same Martian alphabet, so the intercepted text can look quite different from what was sent.
• Linguistic structure matters. In Martian there are relations between two consecutive characters: some characters are more likely to precede a given character than others (the same happens in English, where an 'h' is more likely to have been preceded by a 't' than by a 'q').

Fortunately, for every pair of alphabet characters we know the probability that a received character $y$ was actually sent as the true character $x$, and the probability that a character $x_i$ appears in a clean Martian word given that its immediate predecessor was $x_{i-1}$.

Given all these probabilities, Sascha wants the maximum-likelihood text of a received message: the most likely word the Martians originally sent. Write a program that computes it for several intercepted messages across several Martian dialects.

Formally, for an intercepted message $o_1 o_2 \dots o_L$ and a candidate original message $x_1 x_2 \dots x_L$ of the same length, the likelihood is

$$\left(\prod_{k=1}^{L} e_{x_k o_k}\right)\left(\prod_{k=2}^{L} s_{x_{k-1} x_k}\right),$$

where $e_{xy}$ is the probability that a received character $y$ was originally $x$, and $s_{pq}$ is the probability that character $q$ immediately follows character $p$. You must output the $x_1 \dots x_L$ that maximizes this likelihood.

As a small example, take a local alphabet with only the characters 'a' and 'b', with the receiving-error probabilities and character-succession probabilities shown below.

Receiving error probabilities (row = true character $x$, column = received character $y$; each entry is the probability that a received $y$ was originally sent as $x$):

Character succession probabilities (row = previous character $x_{i-1}$, column = current character $x_i$; each entry is the probability that the current character has the row character as its immediate predecessor):

If the intercepted message is just 'a', it could originally have been either 'a' or 'b'. With no previous character, only the error probabilities matter, and the maximum-likelihood message turns out to be 'a', with probability 0.9.

To extend the example, if the intercepted message is 'ab' we also need the succession probabilities. The probability that the original message was 'aa' is the product of three factors: that the received 'a' was originally 'a' ($0.9$), that the received 'b' was originally 'a' ($0.1$), and that 'a' follows a previous 'a' ($0.8$), giving $0.9 \times 0.1 \times 0.8 = 0.072$. Similarly, 'bb', 'ab', and 'ba' have probabilities $0.1 \times 0.9 \times 0.95 = 0.0855$, $0.9 \times 0.9 \times 0.05 = 0.0405$, and $0.1 \times 0.1 \times 0.2 = 0.002$. The largest is 'bb', so the maximum-likelihood message is 'bb'.

In every case you are asked about, the maximum-likelihood message is unique.

The first line contains an integer $n$, the number of test cases.

Each test case has the following format:

• An integer $a$ ($0 < a < 30$), the number of characters in the local Martian alphabet.
• A line with the $a$ distinct alphabet characters $c_1, c_2, \dots, c_a$, separated by single spaces. Alphabet characters are never whitespace.
• $a$ lines of receiving-error probabilities, in the order the characters were listed. Line $i$ corresponds to the true character $c_i$ and contains $a$ floating-point numbers $e_{i1}, e_{i2}, \dots, e_{ia}$ separated by single spaces. The value $e_{ij}$ ($0 \le e_{ij} \le 1$) is the probability that an observed character $c_j$ was originally sent as $c_i$ (so $\sum_{i=1}^{a} e_{ij} = 1$ for every $j$).
• $a$ lines of character-succession probabilities, in the same order. Line $i$ corresponds to the case where $c_i$ is the immediate predecessor and contains $a$ floating-point numbers $s_{i1}, s_{i2}, \dots, s_{ia}$ separated by single spaces. The value $s_{ij}$ is the probability that a character $c_j$ has $c_i$ as its immediate predecessor (so $\sum_{i=1}^{a} s_{ij} = 1$ for every $j$).
• An integer $w$ ($0 < w < 50$), the number of intercepted messages in this alphabet.
• $w$ lines, each an intercepted message. Every message is non-empty, case-sensitive, at most 300 characters long, and consists only of characters from the local alphabet.

No floating-point number has more than 10 digits after the decimal point.

For each intercepted message, in every test case, output a single line containing the maximum-likelihood original Martian message for that intercepted message.