Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1077
Genetic Combinations

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Statement of the Problem

The population of the small village of Zombiniville is famous fir its genetic characteristics. The inhabitants present only 5 variations on 4 aspects (hair, eyes, nose and feet). Two research companies, Gentec and Genco, tabulated an extensive series of data on the inhabitants of Zombiniville.

Both companies used symbols for the 4 aspects and its variations. Gentec used the groups (A, B, C, D, E), (F, G, H, I, J), (K, L, M, N, O) and (P, Q, R, S, T), which Genco used (a, b, c, d, e), (f, g, h, i, j), (k, l ,m, n, o) and (p, q, r, s, t), but not necessarily for the same group or in the same order inside a group. For example, the group (A, B, C, D, E) from Gentec could correspond to (r, p, t, s, q) from Genco. In other words, "A" corresponds to "r", "B" corresponds to "p", "C" to "t", "D" to "s" and "E" to "q".

Recently the two companies reached an agreement and decided to exchange their research results. However, a group of international activists against human genetic research invaded the offices of the two companies and destroyed part of the reports - exactly the interpretation of the codes.

You and your team were hired to develop a program to establish a relationship among the two notations. As the companies don't want to waste its capital at random, they prepared a battery of tests for your program, before buying it.

Input Format

Each test case has the following data:

1. A line with n, the number of individuals in the test case. You can assume that 0 < n < 64.
2. A line with n descriptions (one for each individual) in the Gentec notation. Each notation is constituted by 4 characters, the first in the interval A-E, the second in the interval F-J, the third in K-O and the last in P-T. A notation is separated from the following by exactly one blank space.
3. A line with n descriptions (for the same individuals, in the same order) in the Genco notation. Each notation is also constituted by 4 characters, the first in the interval a-e, the second in the interval f-j, the third in k-o and the last in p-t. Again, each notation is separated from the following by exactly one blank space.

After a test case, a new one begins. The end of test cases is indicated by n = 0.

You can assume that the test cases are well formed. There are no errors in the input data.

Output Format

For each test case, an association table should be supplied, as in the example below. Note that the pairs are printed in alphabetical order of the capital letters, five per line. Obviously, Gentec and Genco are testing your program, and they don't supply their real data. You can assume that the association table is changed between test cases. You should print only the associations that are unequivocally determined. If there are two or more possibilities for a given letter, you should print a question mark after this letter.

Sample Input

egmr dgnr ehlp egnr dgms
agnp afnp bhmp afnt efkr chkq agnp ailr dhkt bhkt eikp bgor

Sample Output

Test #1:
A-g B-h C-? D-? E-?
F-n G-m H-l I-? J-?
K-s L-? M-p N-r O-?
P-e Q-d R-? S-? T-?
Test #2:
A-a B-b C-c D-d E-e
F-f G-g H-h I-I J-j
K-k L-l M-m N-n O-o
P-p Q-q R-r S-s T-t

Source: South America 2001
Submit    Status