Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
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.
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.
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.
5 AGNP AFNQ BHMP AFNP AGKQ egmr dgnr ehlp egnr dgms 12 AGNP AFNP BHMP AFNT EFKR CHKQ AGNP AILR DHKT BHKT EIKP BGOR agnp afnp bhmp afnt efkr chkq agnp ailr dhkt bhkt eikp bgor 0
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