C(O|W|A*РД*|S)* КРОСВОРД Головоломка
Перший кросворд був опублікований 21 грудня 1913 року Артуром Вінном. На честь сторіччя з дня винаходу свого двоюрідного прадіда, Джон "Трус" Вінн-1 намагався створювати кросворди. Він був настільки боязким, що кожного разу, коли придумував хитромудру підказку для слова, починав хвилюватися, що його звинуватять у невдалому виборі. Врешті-решт, він обирав нудні підказки, що робило його загадки менш цікавими.
Одного разу йому прийшла в голову блискуча ідея: створити головоломку, в якій значення слів не має значення, але яка все ще буде цікавою. Він поділився цією ідеєю з колегами, і вони визнали її досить інтригуючою. Вони навіть назвали його головоломки "Кросворди Труса" на честь його прізвиська.
Однак створення кросворду Труса виявилося нелегким завданням. Незважаючи на те, що не потрібно думати про значення слів, було складно перевірити, чи має головоломка лише один набір відповідей. Коли день сторіччя наближався, Джон почав хвилюватися, чи встигне він створити щось цікаве вчасно. Давайте допоможемо Джону написати програму, яка розв'язує кросворди Труса.
Кожна головоломка складається з h × w клітинок, що містять h горизонтальних ключів і w вертикальних. Ключі (clue) є регулярними виразами, записаними мовою, визначеною наступним синтаксисом БНФ.
Таблиця 1. БНФ синтаксис мови.
Ключі (позначаються нижче через p і q) відповідають словам (позначається нижче через s) згідно з наступними правилами.
^p$ відповідає s, якщо p відповідає s.
p|q відповідає рядку s, якщо p і/або q відповідає s.
pq відповідає рядку s, якщо існують такі s_1 і s_2, що s_1s_2 = s, p відповідає s_1, і q відповідає s_2.
p* відповідає рядку s, якщо s порожнє, або існують такі s_1 і s_2, що s_1s_2 = s, p відповідає s_1 і p* відповідає s_2.
Кожен із символів A, B, ..., Z відповідає своїй же букві.
(p) відповідає s, якщо p відповідає s.
. є скороченням (A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z).
Нижче наведено приклад кросворду Труса з відповідями, заповненими в клітинках.
Java Specific: Подані програми на Java не можуть використовувати класи з пакету java.util.regex.
C++ Specific: Подані програми на C++ не можуть використовувати клас std::regex.
_________________
^1Усі персонажі, що з'являються в цій задачі, крім Артура Вінна, є вигаданими. Будь-яка схожість з реальними особами, живими чи мертвими, є випадковою.
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких представляє головоломку у наступному форматі.
h w
p_1
p_2
...
p_h
q_1
q_2
...
q_w
Тут, h і w представляють вертикальну та горизонтальну кількість клітинок відповідно, де 2 ≤ h, w ≤ 4. p_i та q_j є підказками для i-го рядка та j-го стовпця відповідно. Будь-яка підказка має не більше 512 символів.
Останній набір даних завершується рядком з двох нулів. Ви можете припустити, що у вхідних даних не більше 30 наборів.
Вихідні дані
Для кожного набору даних, коли головоломка має унікальний набір відповідей, виведіть його у вигляді h рядків з w символів. Коли головоломка не має набору відповідей або має більше одного набору відповідей, виведіть "none" або "ambiguous" без подвійних лапок відповідно.