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...