Drift Puzzle
Обычная головоломка включает в себя последовательность из трех кадров (F_1, F_2, F_3) анимации с вопросом о "наиболее логичном" четвертом кадре F_4. Например:
Обычно такая головоломка представлена в виде вопроса с несколькими вариантами ответов, что может быть скучно. Более интересная задача — найти четвертый кадр напрямую!
Мы будем рассматривать кадры анимации, которые создаются по следующим правилам:
Каждый кадр F_i — это сетка высотой h и шириной w.
Каждый кадр F_i содержит n различных объектов m_1 = A, m_2 = B, m_3 = C, ..., m_n = (буква).
Каждый объект m_j в каждом кадре занимает одну из h×w ячеек и может перекрываться.
Если два объекта m_j и m_k, j < k, занимают одну и ту же ячейку, виден будет только m_j (т.е. объект с меньшим индексом).
Каждый объект m_j имеет фиксированную, ненулевую "скорость дрейфа": от F_i до F_i+1 m_j перемещается на 1 единицу в одном из восьми возможных (горизонтальном, вертикальном или диагональном) направлений.
Если объект выходит за пределы сетки, он "оборачивается" на противоположную сторону (или угол).
В показанном примере мы можем сделать вывод, что A дрейфует на восток; B дрейфует на юго-запад; C дрейфует на север; D дрейфует на север; и E дрейфует на северо-запад. В F_2 B и C занимают одну и ту же ячейку, поэтому виден только B. В F_3 B дрейфует за западную стену и оборачивается на восточной стороне (одновременно перемещаясь на юг на одну единицу). Используя приведенную выше информацию, мы можем экстраполировать траекторию каждого объекта и найти F_4:
Поскольку объекты могут перекрывать друг друга, F_1, F_2 и F_3 могут не предоставлять достаточно информации для определения скоростей каждого объекта. Поэтому F_4 может иметь несколько решений (см. пример входных данных 2); когда это происходит, вы должны вывести сообщение об ошибке. Иногда объекты могут иметь множество возможных скоростей, но уникальное решение для F_4 все же существует (см. пример входных данных 3); в этом случае F_4 четко определен и должен быть решен.
Входные данные
Первая строка входных данных содержит количество тестов N, 1 ≤ N ≤ 50.
Каждый тест начинается со строки, содержащей целые числа h, w и n, разделенные пробелом. Следуют h строк. В каждой строке i, 1 ≤ i ≤ h, даны три строки длины w a_i, b_i и c_i, разделенные пробелом. Текстовый блок a_1, a_2, ..., a_h, при вертикальном сложении, определяет F_1. Аналогично, b_1, b_2, ..., b_h и c_1, c_2, ..., c_h определяют F_2 и F_3 соответственно.
h — это высота каждого кадра и удовлетворяет 3 ≤ h ≤ 10.
w — это ширина каждого кадра и удовлетворяет 3 ≤ w ≤ 10.
n — это количество различных объектов и удовлетворяет 1 ≤ n ≤ 26.
Для 1 ≤ i ≤ h, каждая a_i, b_i и c_i — это строки длины w, состоящие из заглавных букв "A"-"Z" (для объектов) или точки "." (для пустых мест).
F_1, F_2 и F_3 из входных данных будут следовать правилам построения анимации, изложенным выше, поэтому F_4 гарантированно будет иметь хотя бы одно решение.
Выходные данные
Для каждого теста, если существует уникальный F_4, то выведите его в том же формате, что и входные данные, т.е. в виде h строк длины w. В противном случае выведите "Существует несколько решений" на одной строке. Выведите пустую строку между тестами, но не после последнего теста.
Для теста 2 два возможных решения для F_4 это
ABC ABC
DE. DEF
в зависимости от того, дрейфует ли F на север или на запад; поэтому существует несколько решений.
Для теста 3 G может дрейфовать на восток, на юг или на юго-восток, но все три случая приведут к одному и тому же F_4, поэтому существует уникальное решение.
Для теста 4 B-D покрыты A, а F-Z покрыты A или E. Поэтому расположение некоторых блоков неоднозначно. Однако существует уникальное решение.
Для теста 5 два возможных F_4 это
..... .....
..C.. ..C..
..... .....
A.... A..D.
.B... .B...