Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Substitution Cipher
Time Limit: 2000MSMemory Limit: 10000K
Total Submissions: 1080Accepted: 194

Description

Antique Comedians of Malidinesia would like to play a new discovered comedy of Aristofanes. 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 correspondece. 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 neccessary 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 lexicografically 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. 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.'.

Sample Input

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

Sample Output

abcde
Message cannot be decrypted.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator