Weaker than Planned#3431
The committee members of the Kitoshima programming contest decided to use cryptographic software for their secret communication. They asked Kodai Software to develop cryptographic software employing a cipher based on highly sophisticated mathematics.
According to IT project reports, many projects are not delivered on time, on budget, and with required features and functions. This was also the case here: Kodai Software failed to deliver the cipher by the appointed deadline and proposed temporarily using a simpler substitution cipher instead. Although the committee members were displeased and strongly requested that the full-featured product be delivered, they reluctantly agreed to use this inferior product temporarily.
From here on, we refer to the text before encryption as plaintext, and the text after encryption as ciphertext.
This simple cipher replaces letters in the plaintext according to a substitution rule specified by a set of unordered pairs of letters. The order of the letters in a pair does not matter, so the pair has the same meaning as the pair . In one substitution rule, each letter can appear in at most one pair. When a letter in a pair appears in the plaintext, it is replaced with the other letter in the pair. Letters not specified in any pair remain unchanged.
For example, substituting the plaintext
ABCDEFGHIJKLMNOPQRSTUVWXYZ
according to the substitution rule \{ (A, Z), (B, Y) \} results in the following ciphertext:
ZYCDEFGHIJKLMNOPQRSTUVWXBA
This may be a good opportunity for us, since the substitution rule appears to be weak against cryptanalysis. We may be able to infer communications between committee members. Your task is to develop a deciphering program that finds the plaintext messages given the ciphertext messages.
A ciphertext message consists of one or more ciphertext words. A ciphertext word is generated from a plaintext word using a substitution rule. You are given a list of candidate words containing all possible words that may appear in the plaintext; no other words will be used. Some words in the list may not actually appear in the plaintext.
It is guaranteed that there is always at least one sequence of candidate words from which the given ciphertext can be obtained by some substitution rule. However, in some cases, it may be impossible to uniquely determine the plaintext given the ciphertext and the list of candidate words.
The input consists of multiple datasets, each containing a ciphertext message and a list of candidate words in the following format:
n word_1 word_2 word_n sequence
The first line contains a positive integer , the number of candidate words. Each of the next lines contains one of the candidate words. The last line, sequence, is a sequence of one or more ciphertext words separated by single spaces and terminated with a period.
You may assume that the number of characters in each sequence is greater than and less than or equal to , including spaces and the period. The number of candidate words, , does not exceed . Only the uppercase English letters to are used in the words, and each word is between and characters long, inclusive.
A line containing a single indicates the end of input.
For each dataset, your program should print the deciphered message on a single line. Two adjacent words in the output should be separated by a single space, and the last word should be followed by a single period.
If it is impossible to uniquely identify the plaintext, the output line should consist of a single hyphen immediately followed by a period.
Example 1