Drift Puzzle
A common puzzle involves listing a sequence of three frames (F_1, F_2, F_3) of an animation, and asking for the "most logical" fourth frame F_4. For example:
Usually the puzzle is posed as multiple-choice question. This is boring. A more interesting problem is to find the fourth frame directly!
To be precise, we will consider animation frames that are constructed using the following rules:
Every frame F_i is a grid with height h and width w.
Every frame F_i contains n distinct objects m_1 = A, m_2 = B, m_3 = C, ..., m_n = (letter).
Each object m_j in each frame is located in one of h×w cells, and may overlap.
If two objects m_j and m_k, j < k occupy the same cell, then only m_j (i.e. the object with lesser index) would be visible.
Each object m_j has a fixed, non-zero "drift velocity": From F_i to F_i_{+1}, m_j travels 1 unit in one of eight possible (horizontal, vertical or diagonal) directions.
If an object moves outside the grid, it "wraps around" to the opposite side (or corner).
In the example shown, we can deduce that A drifts eastward; B drifts south-westward; C drifts northward; D drifts northward; and E drifts north-westward. In F_2, B and C occupy the same cell, so only B is visible. In F_3, B drifts beyond the west wall, and wraps around on the east side (while also moving south by one unit). Using the above information, we can extrapolate the trajectory of each object, and find F_4:
Since objects cover one another, F_1, F_2 and F_3 may not provide enough information to solve for the velocities of each object. Therefore F_4 can have multiple solutions (see Sample Input case 2); when this happens you should output an error message. Sometimes objects can have many possible velocities, but a unique solution for F_4 would still exist (see Sample Input case 3); in this case F_4 is well-defined, and should be solved.
Input
The first input line contains the number of test cases N, 1 ≤ N ≤ 50.
Each test case begins with a line containing integers h, w and n, separated by space. h lines follow. On each line i, 1 ≤ i ≤ h, three space-separated length-w strings a_i, b_i and c_i are given. The text block a_1, a_2, ..., a_h, when stacked vertically, specifies F_1. Similarly, b_1, b_2, ..., b_h and c_1, c_2, ..., c_h specify the F_2 and F_3, respectively.
h is the height of each frame, and satisfies 3 ≤ h ≤ 10.
w is the width of each frame, and satisfies 3 ≤ w ≤ 10.
n is the number of distinct masses, and satisfies 1 ≤ n ≤ 26.
For 1 ≤ i < h, each a_i, b_i and c_i are length-w strings consists of upper case alphabets "A"-"Z" (for objects) or the period "." (for empty spaces).
F_1, F_2 and F_3 from inputs will follow animation construction rules outline above, so F_4 is guaranteed to have at least one solution.
Output
For each test case, if a unique F_4 exists, then print it in the same format as the input, i.e. as h lines of length-w strings. Otherwise print "Multiple solutions exist" on a single line. Print an empty line between test cases, but not after the last test case.
For Test Case 2, two possible solutions for F_4 are
ABC ABC
DE. DEF
depending whether F drifts northward or drifts westward; so multiple solutions exist.
For Test Case 3, G may drift eastward, southward or south-eastword, but all three cases would lead to the same F_4, so a unique solution exists.
For Test Case 4, B-D are covered by A, and F-Z are covered by A or E. Therefore the location of some blocks are ambiguous. However, a unique solution exists.
For Test Case 5, Two possible F_4's are
..... .....
..C.. ..C..
..... .....
A.... A..D.
.B... .B...