SCYPHER - Substitution Cipher

no tags 

Antique Comedians of Malidinesia would like to play a new discovered comedy of Aristophanes. Putting it on a stage should be a big surprise for the audience so all the preparations must be kept absolutely secret. The ACM director suspects one of his competitors of reading his correspondence. To prevent other companies from revealing his secret, he decided to use a substitution cipher in all the letters mentioning the new play.

Substitution cipher is defined by a substitution table assigning each character of the substitution alphabet another character of the same alphabet. The assignment is a bijection (to each character exactly one character is assigned -- not necessarily different). The director is afraid of disclosing the substitution table and therefore he changes it frequently. After each change he chooses a few words from a dictionary by random, encrypts them and sends them together with an encrypted message. The plain (i.e. non-encrypted) words are sent by a secure channel, not by mail. The recipient of the message can then compare plain and encrypted words and create a new substitution table.

Unfortunately, one of the ACM cipher specialists have found that this system is sometimes insecure. Some messages can be decrypted by the rival company even without knowing the plain words. The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ap is lexicographically smaller than b1b2 ... bq if there exists an integer i, i <= p, i <= q, such that aj=bj for each j, 1 <= j < i and ai < bi.

The director is interested in which of his messages could be read by the rival company. You are to write a program to determine that.

Input

The input consists of N cases (equal to about 1000). The first line of the input contains only positive integer N. Then follow the cases. The first line of each case contains only two positive integers A, 1 <= A <= 26, and K, separated by space. A determines the size of the substitution alphabet (the substitution alphabet consists of the first A lowercase letters of the English alphabet (a--z) and K is the number of encrypted words. The plain words contain only the letters of the substitution alphabet. The plain message can contain any symbol, but only the letters of the substitution alphabet are encrypted. Then follow K lines, each containing exactly one encrypted word. At the next line is encrypted message.

Output

For each case, print exactly one line. If it is possible to decrypt the message uniquely, print the decrypted message. Otherwise, print the sentence 'Message cannot be decrypted.'.

Example

Input:
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac

Output:
abcde
Message cannot be decrypted.
Warning: large Input/Output data, be careful with certain languages

hide comments
ebd: 2010-03-23 11:52:08

You should add cases like:
1 4 6
a
bc
bd
bdc
bdb
d
bd

Tasnim Khan: 2009-12-03 21:02:56

encrypted message contains spaces commas ... so be careful with segmentation faults


Added by:adrian
Date:2004-06-06
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM Central European Programming Contest, Prague 1998