Дрейфуюча загадка#3826
Загадка часто полягає в тому, щоб перерахувати послідовність з трьох кадрів (F_1, F_2, F_3) анімації та визначити найлогічніший четвертий кадр F_4. Наприклад:
Зазвичай загадка подається у вигляді питання з кількома варіантами відповіді, що може бути нудним. Більш цікавою задачею є знайти четвертий кадр безпосередньо!
Ми розглянемо кадри анімації, які створюються за такими правилами:
Кожен кадр F_i є сіткою з висотою і шириною .
Кожен кадр F_i містить різних об'єктів m_1 = A, m_2 = B, m_3 = C, ..., m_n = \text{(літера)}.
Кожен об'єкт m_j у кожному кадрі розташований в одній з h \times w клітинок і може перекриватися.
Якщо два об'єкти m_j і m_k, j < k займають ту саму клітинку, то буде видно лише m_j (тобто об'єкт з меншим індексом).
Кожен об'єкт m_j має фіксовану, ненульову "швидкість дрейфу": від F_i до F_{i+1}, m_j переміщується на одиницю в одному з восьми можливих (горизонтальному, вертикальному або діагональному) напрямків.
Якщо об'єкт виходить за межі сітки, він "обертається" на протилежну сторону (або кут).
У наведеному прикладі ми можемо зробити висновок, що дрейфує на схід; дрейфує на південний захід; дрейфує на північ; дрейфує на північ; і дрейфує на північний захід. У F_2 і займають ту саму клітинку, тому видно лише . У F_3 дрейфує за західну стіну і обертається на східну сторону (при цьому переміщуючись на південь на одну одиницю). Використовуючи цю інформацію, ми можемо екстраполювати траєкторію кожного об'єкта і знайти F_4:
Оскільки об'єкти перекривають один одного, F_1, F_2 і F_3 можуть не надати достатньо інформації для визначення швидкостей кожного об'єкта. Тому F_4 може мати кілька рішень (див. приклад вхідних даних ); коли це відбувається, ви повинні вивести повідомлення про помилку. Іноді об'єкти можуть мати багато можливих швидкостей, але унікальне рішення для F_4 все ж існуватиме (див. приклад вхідних даних ); у цьому випадку F_4 чітко визначений і повинен бути вирішений.
Перший рядок введення містить кількість тестових випадків , 1 \leq N \leq 50.
Кожен тестовий випадок починається з рядка, що містить цілі числа , і , розділені пробілом. Далі йдуть рядків. У кожному рядку , 1 \leq i \leq h, наведено три рядки довжини 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 відповідно.
— це висота кожного кадру і задовольняє умову 3 \leq h \leq 10.
— це ширина кожного кадру і задовольняє умову 3 \leq w \leq 10.
— це кількість різних об'єктів, і задовольняє умову 1 \leq n \leq 26.
Для 1 \leq i \leq h, кожен a_i, b_i і c_i є рядками довжини , що складаються з великих літер алфавіту "A"–"Z" (для об'єктів) або крапки "." (для порожніх місць).
F_1, F_2 і F_3 з введення будуть слідувати правилам побудови анімації, описаним вище, тому F_4 гарантовано матиме принаймні одне рішення.
Для кожного тестового випадку, якщо існує унікальний F_4, то виведіть його у тому ж форматі, що й вхідні дані, тобто у вигляді рядків довжини . Інакше виведіть Multiple solutions exist в одному рядку. Виведіть порожній рядок між тестовими випадками, але не після останнього тестового випадку.
Для тестового випадку два можливих рішення для F_4 є
ABC ABC
DE. DEF
залежно від того, чи дрейфує на північ, чи на захід; тому існує кілька рішень.
Для тестового випадку , може дрейфувати на схід, на південь або на південний схід, але всі три випадки призведуть до одного і того ж F_4, тому існує унікальне рішення.
Для тестового випадку , – покриті , а – покриті або . Тому розташування деяких блоків є неоднозначним. Однак існує унікальне рішення.
Для тестового випадку , два можливих F_4 є
..... .....
..C.. ..C..
..... .....
A.... A..D.
.B... .B...
Приклад 1