C(O|W|A*RD*|S)* CROSSWORD Puzzle
Первый кроссворд был опубликован 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).
Below is an example of a Coward’s crossword puzzle with the answers filled in the cells.
Java Specific: Submitted Java programs may not use classes in the java.util.regex package.
C++ Specific: Submitted C++ programs may not use the std::regex class.
_________________
^1All characters appearing in this problem, except for Arthur Wynne, are fictitious. Any resemblance to real persons, living or dead, is purely coincidental.
Входные данные
The input consists of multiple datasets, each of which represents a puzzle given in the following format.
h w
p_1
p_2
...
p_h
q_1
q_2
...
q_w
Here, h and w represent the vertical and horizontal numbers of cells, respectively, where 2 ≤ h, w ≤ 4. The p_i and q_j are the across and down clues for the i-th row and j-th column, respectively. Any clue has no more than 512 characters.
The last dataset is followed by a line of two zeros. You may assume that there are no more than 30 datasets in the input.
Выходные данные
For each dataset, when the puzzle has a unique set of answers, output it as h lines of w characters. When the puzzle has no set of answers, or more than one set of answers, output "none" or "ambiguous" without double quotations, respectively.