치환 암호

말리디네시아 고전 희극단은 새로 발견된 아리스토파네스의 희극을 무대에 올리려 한다. 관객에게 큰 놀라움을 주기 위해 모든 준비는 철저히 비밀에 부쳐야 한다. 단장은 경쟁자가 자신의 서신을 몰래 읽고 있다고 의심하여, 새 연극을 언급하는 모든 편지를 치환 암호로 암호화한다.

치환 암호는 치환표로 정의된다. 치환표는 어떤 알파벳의 각 문자에 같은 알파벳의 문자 하나를 대응시키며, 이 대응은 전단사(일대일 대응)이다. 각 문자에는 정확히 하나의 문자가 대응되며, 그 문자는 원래 문자와 같을 수도 있다.

단장은 치환표가 새어 나갈까 두려워 이를 자주 바꾼다. 표를 바꿀 때마다 사전에서 단어 몇 개를 무작위로 골라 암호화한 뒤, 암호화된 메시지와 함께 보낸다. 암호화하지 않은 원래 단어들은 우편이 아니라 안전한 경로로 전달되므로, 수신자는 원래 단어와 암호화된 단어를 비교하여 치환표를 복원할 수 있다.

그런데 이 방식은 때때로 안전하지 않다. 경쟁자가 원래 단어를 전혀 보지 못해도 암호화된 단어만으로 메시지를 해독할 수 있는 경우가 있기 때문이다. 그 이유는 단장이 고른 단어들의 순서를 절대 바꾸지 않으며, 사전이 사전순으로 정렬되어 있기 때문이다. 문자열 a_1 a_2 ... a_p가 b_1 b_2 ... b_q보다 사전순으로 앞선다는 것은, 어떤 정수 i (i <= p, i <= q)가 존재하여 1 <= j < i인 모든 j에 대해 a_j = b_j이고 a_i < b_i임을 뜻한다.

각 메시지가 유일하게 해독될 수 있는지 판정하는 프로그램을 작성하라.

첫 줄에는 케이스의 수 N(양의 정수)이 주어진다. 이어서 각 케이스가 주어진다.

각 케이스의 첫 줄에는 두 양의 정수 A와 K가 공백으로 구분되어 주어지며, 1 <= A <= 26이다. A는 치환 알파벳의 크기로, 치환 알파벳은 영어 알파벳의 처음 A개의 소문자(a-z)로 이루어진다. K는 암호화된 단어의 개수이다.

다음 K개의 줄에는 각각 암호화된 단어가 정확히 하나씩 주어진다. 이 단어들은 원문 기준 사전순 오름차순으로 나열된 사전 단어들을 암호화한 것이다. 모든 원래 단어는 치환 알파벳의 문자만 사용한다.

그다음 줄에는 암호화된 메시지가 주어진다. 원래 메시지는 어떤 문자든 포함할 수 있으나, 치환 알파벳의 문자만 암호화되며 나머지 문자는 그대로 유지된다.

각 케이스마다 정확히 한 줄을 출력한다. 메시지를 유일하게 해독할 수 있으면 해독된 메시지를 출력하고, 그렇지 않으면 Message cannot be decrypted.를 출력한다.