5408번 - Message 다국어

When little Sascha grew up, she lost her bad habit of pronouncing words in ways that were most easy for her, but did not always match the correct pronunciation. However, she never lost the linguistic creativity she used to show as a little girl. When the Earth Allied Forces (EAF) discovered she also had brilliant mathematical insights and a knack for puzzles and secret messages, she was immediately offered the position of Head of the EAF Intelligence Department.

Sascha's current task is interpreting intercepted internal messages of the hostile Mars Federation. Although Martian messages always consist of just one word, her task turns out not to be easy, as two factors influence the content of the intercepted message:

Extraterrestrial environment conditions are so bad that errors can occur in intercepted messages, causing them to be quite obfuscated compared to the originally sent text. If such errors occur, the erroneous characters will be characters from the Martian alphabet, just as the original characters.
Furthermore, linguistic characteristics play an important role. In Martian, there are relations between two subsequent characters: for a given character, some characters are more likely predecessors than others (note that something similar occurs in English: for example, a 'h' in a word will more likely have been preceded by a 't' than by a 'q').

Fortunately, probabilities that a received character y actually was sent as an original Martian character x is known for all alphabet characters, as well as the probabilities that a certain character x_i occurs in a clean Martian word if it was preceded by a Martian character x_i−1.

Given all these probabilities, Sascha wants to find the so-called maximum likelihood text for a received message, which is the most likely message the Martians originally sent. As senior programmer in the EAF Intelligence Department, you must write a program for her, achieving this goal for several intercepted messages in several local Martian dialects.

To give a simple example, consider a local Martian alphabet only consisting of the characters 'a' and 'b' and let the receiving error probabilities and character succession probabilities be as shown in Table 2. If the intercepted message just consists of an 'a', this can either originally have been an 'a' or a 'b'. With no previous characters available, only the error probabilities are considered: it then turns out that the maximum likelihood message is an 'a' as well, with probability 0.9.

Table 2: Example Receiving Error Probabilities (left) and Character Succession Probabilities (right).

To extend the example, if the intercepted message was 'ab', we also need the character succession probabilities. The probability that the original message was 'aa' is

p(received 'a' indeed was originally sent as 'a') × p(received 'b' was originally sent as 'a') × p(character 'a' succeeds previous 'a') = 0.9 × 0.1 × 0.8.

Similarly, the probability that the original message was 'bb', 'ab' or 'ba' are 0.1 × 0.9 × 0.95, 0.9 × 0.9 × 0.05 and 0.1 × 0.1 × 0.2, respectively. Hence, the maximum likelihood message now is 'bb'. In all cases asked for, there will always be a unique maximum likelihood message.

• The first line of input consists of the integer number n, the number of test cases;
• Then, for each test case: 
  • An integer number a (0 < a < 30), which is the number of characters in the local Martian alphabet; 
  • A line containing the a unique characters c₁,c₂,...,c_a of the local Martian alphabet, separated by single spaces. Whitespace characters will not occur in the alphabet; 
  • a lines, specifying receiving error probabilities for the a alphabet characters in the order in which they were presented. The ith line corresponds to the error probabilities for the original alphabet character c_i and contains: 
    • a floating point numbers e_i1,e_i2,...,e_ia, separated by single spaces. Number e_ij (0 ≤ e_ij ≤ 1) indicates the probability that an observed character c_j originally was sent as the character c_i (hence Σ^a_i=1e_ij = 1.00000000); 
  • a lines, specifying character succession probabilities for the a alphabet characters in the order in which they were presented. The ith line corresponds to the character succession probabilities for cases where the original alphabet character c_i was the immediate predecessor and contains: 
    • a floating point numbers s_i1,s_i2,...,s_ia, separated by single spaces. Number sij indicates the probability that a certain character c_j has character c_i as immediate predecessor (hence Σ^a_i=1s_ij = 1.00000000); 
  • An integer number w (0 < w < 50), indicating the number of intercepted messages in the local Martian alphabet specified; 
  • Then, for each intercepted message: 
  • A line containing the intercepted message. These messages are non-empty, case-sensitive and will not exceed 300 characters in length. 

Given floating point numbers never have more than 10 decimal numbers following the separator

For each message in each test case, the output will consist of a single line with a single string: the maximum likelihood original Martian message given the intercepted message.