Weaker than Planned

Time limit1sMemory limit128 MB

Summary

Given candidate plaintext words and a ciphertext message, recover the plaintext under one unknown letter-pair substitution, or report that it is not unique.

Level: Hard8 of 10
Topics: Backtracking, String, Hash map, Brute force
Solved: No attempts yet

Problem

The organizers of a programming contest planned to use cryptographic software for their private communication, so they hired a company to build a cipher based on advanced mathematics.

As often happens with software projects, the product was not delivered on time. The company could not finish the intended cipher by the deadline and instead offered a much simpler substitution cipher for the time being. The organizers were unhappy, but reluctantly agreed to use this weaker product for now.

We call the text before encryption the plaintext and the text after encryption the ciphertext.

This simple cipher replaces letters in the plaintext according to a substitution rule given as a set of pairs. A pair consists of two letters and is unordered, so the pair (A, B) means exactly the same as (B, A). In one substitution rule each letter may appear in at most one pair. Whenever a letter that belongs to a pair occurs in the plaintext, it is replaced by the other letter of that pair; letters that appear in no pair are left unchanged.

For example, applying the rule {(A, Z), (B, Y)} to the plaintext

ABCDEFGHIJKLMNOPQRSTUVWXYZ

produces the ciphertext

ZYCDEFGHIJKLMNOPQRSTUVWXBA

Because this substitution cipher is weak, there is a chance to read the organizers' messages. Your task is to write a program that recovers the plaintext from a given ciphertext.

A ciphertext message consists of one or more ciphertext words. Each ciphertext word is obtained from a plaintext word using one single substitution rule that is shared by the entire message. You are also given a list of candidate words: every plaintext word must be taken from this list, and no other word may appear. Some words in the list might not be used at all.

It is guaranteed that at least one sequence of candidate words produces the given ciphertext under some substitution rule. However, the plaintext cannot always be identified uniquely from the ciphertext together with the candidate list.

Input

The input consists of several datasets. Each dataset describes one ciphertext message together with a list of candidate words, in the following format.

n
word_1
...
word_n
sequence

The first line contains a positive integer $n$ , the number of candidate words. Each of the next $n$ lines holds one candidate word. The final line, sequence, is a list of one or more ciphertext words separated by single spaces and terminated by a period.

You may assume that each sequence line contains more than $1$ and at most $80$ characters, counting the spaces and the terminating period. The number of candidate words satisfies $1 \le n \le 20$ . Words use only the $26$ uppercase letters A to Z, and each word has length between $1$ and $20$ inclusive.

A line containing a single zero marks the end of the input and is not part of any dataset.

Output

For each dataset, print the deciphered message on its own line: the recovered plaintext words separated by single spaces, with a single period right after the last word and no space before it. If the plaintext cannot be determined uniquely, print a single hyphen followed by a period (-.) instead.

Examples3

Example 1

Input

4
A
AND
CAT
DOG
Z XUW ZVX Z YZT.
2
AZ
AY
ZA.
2
AA
BB
CC.
16
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
ABCDEFGHIJKLMNO
A B C D E F G H I J K L M N O ABCDEFGHIJKLMNO.
0

Expected output

A DOG AND A CAT.
AZ.
-.
A B C D E F G H I J K L M N O ABCDEFGHIJKLMNO.

Example 2
Input
```
2
I
IT
XY X.
0
```
Expected output
```
IT I.
```

Example 3

Input

4
A
AND
CAT
DOG
Z XUW ZVX Z YZT.
0

Expected output

A DOG AND A CAT.