메시지

어린 시절의 Sascha는 단어를 올바른 발음이 아니라 자신이 발음하기 가장 편한 대로 소리 내는 버릇이 있었다. 어른이 되면서 그 버릇은 사라졌지만, 어릴 적 보여 주던 언어적 창의력만큼은 잃지 않았다. 지구 연합군(Earth Allied Forces, EAF)은 그녀가 뛰어난 수학적 통찰력과 퍼즐·암호 해독 재능까지 지녔음을 알아채고, 곧바로 EAF 정보부장을 맡겼다.

Sascha의 현재 임무는 적대 세력인 화성 연방(Mars Federation)의 내부 통신을 가로채 해석하는 것이다. 화성어 메시지는 언제나 단 하나의 단어로 이루어지지만, 실제로 가로챈 메시지의 내용은 두 가지 요인 때문에 해석이 쉽지 않다.

• 외계 환경이 매우 열악해 통신 중 오류가 발생한다. 오류가 나면 해당 글자는 같은 화성어 알파벳에 속한 다른 글자로 바뀌므로, 가로챈 문장은 원래 보낸 문장과 상당히 달라 보일 수 있다.
• 언어적 특성도 중요하게 작용한다. 화성어에서는 연이은 두 글자 사이에 관계가 있어, 어떤 글자 앞에는 특정 글자가 다른 글자보다 더 자주 온다(영어에서도 'h' 앞에는 'q'보다 't'가 올 가능성이 높은 것과 비슷하다).

다행히 모든 알파벳 글자 쌍에 대해, 수신된 글자 $y$가 실제로는 원래 글자 $x$로 전송되었을 확률과, 바로 앞 글자가 $x_{i-1}$일 때 정상적인 화성어 단어에서 글자 $x_i$가 나타날 확률을 알고 있다.

이 확률들이 주어졌을 때, Sascha는 가로챈 메시지에 대한 최대우도(maximum-likelihood) 문장, 즉 화성인들이 원래 보냈을 가능성이 가장 높은 단어를 찾고자 한다. 여러 화성어 방언으로 가로챈 여러 메시지에 대해 이를 계산하는 프로그램을 작성하라.

형식적으로, 가로챈 메시지 $o_1 o_2 \dots o_L$과 같은 길이의 후보 원문 $x_1 x_2 \dots x_L$에 대해 우도(likelihood)는

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

이다. 여기서 $e_{xy}$는 수신된 글자 $y$가 원래 $x$였을 확률이고, $s_{pq}$는 글자 $q$가 바로 앞 글자 $p$ 뒤에 올 확률이다. 이 우도를 최대로 만드는 $x_1 \dots x_L$을 출력해야 한다.

간단한 예로, 글자 'a'와 'b'만으로 이루어진 지역 알파벳을 생각하고 수신 오류 확률과 글자 연접 확률이 아래와 같다고 하자.

수신 오류 확률(행 = 참 글자 $x$, 열 = 수신 글자 $y$이며, 각 칸의 값은 수신된 $y$가 원래 $x$로 전송되었을 확률):

글자 연접 확률(행 = 앞 글자 $x_{i-1}$, 열 = 현재 글자 $x_i$이며, 각 칸의 값은 현재 글자가 그 행의 글자를 바로 앞 글자로 가질 확률):

가로챈 메시지가 'a' 하나뿐이라면 원래 글자는 'a'일 수도, 'b'일 수도 있다. 앞 글자가 없으므로 오류 확률만 고려하면 되고, 그 결과 최대우도 메시지는 확률 0.9로 'a'가 된다.

예를 더 확장해서 가로챈 메시지가 'ab'라면 연접 확률도 필요하다. 원문이 'aa'였을 확률은 세 요인의 곱이다. 수신된 'a'가 원래 'a'였을 확률($0.9$), 수신된 'b'가 원래 'a'였을 확률($0.1$), 'a'가 앞 글자 'a' 뒤에 올 확률($0.8$)을 곱하면 $0.9 \times 0.1 \times 0.8 = 0.072$이다. 마찬가지로 'bb', 'ab', 'ba'의 확률은 각각 $0.1 \times 0.9 \times 0.95 = 0.0855$, $0.9 \times 0.9 \times 0.05 = 0.0405$, $0.1 \times 0.1 \times 0.2 = 0.002$이다. 이 중 가장 큰 값은 'bb'이므로 최대우도 메시지는 'bb'이다.

문제에서 묻는 모든 경우에 대해 최대우도 메시지는 유일하다.

첫째 줄에 테스트 케이스의 개수 정수 $n$이 주어진다.

각 테스트 케이스는 다음 형식으로 주어진다.

• 정수 $a$ ($0 < a < 30$): 지역 화성어 알파벳의 글자 수.
• 한 줄에 알파벳의 서로 다른 글자 $c_1, c_2, \dots, c_a$가 하나의 공백으로 구분되어 주어진다. 알파벳 글자에는 공백 문자가 포함되지 않는다.
• 수신 오류 확률 $a$개 줄. 글자가 나열된 순서를 따르며, $i$번째 줄은 참 글자 $c_i$에 대응하고 공백으로 구분된 실수 $e_{i1}, e_{i2}, \dots, e_{ia}$를 담는다. 값 $e_{ij}$ ($0 \le e_{ij} \le 1$)는 관측된 글자 $c_j$가 원래 $c_i$로 전송되었을 확률이다(따라서 모든 $j$에 대해 $\sum_{i=1}^{a} e_{ij} = 1$).
• 글자 연접 확률 $a$개 줄. 같은 순서를 따르며, $i$번째 줄은 $c_i$가 바로 앞 글자인 경우에 대응하고 공백으로 구분된 실수 $s_{i1}, s_{i2}, \dots, s_{ia}$를 담는다. 값 $s_{ij}$는 글자 $c_j$가 $c_i$를 바로 앞 글자로 가질 확률이다(따라서 모든 $j$에 대해 $\sum_{i=1}^{a} s_{ij} = 1$).
• 정수 $w$ ($0 < w < 50$): 이 알파벳으로 가로챈 메시지의 개수.
• $w$개 줄, 각 줄은 가로챈 메시지 하나이다. 모든 메시지는 비어 있지 않고, 대소문자를 구분하며, 길이는 최대 300자이고, 해당 지역 알파벳의 글자들로만 이루어진다.

모든 실수는 소수점 아래 자릿수가 10자리를 넘지 않는다.

각 테스트 케이스의 가로챈 메시지마다, 그 메시지에 대한 최대우도 원본 화성어 메시지를 한 줄에 하나씩 출력한다.