C(O|W|A*RD*|S)* CROSSWORD Puzzle

Arthur Wynne published the first crossword puzzle on December 21, 1913. To mark the centennial of his great-great-grandfather's invention, John "Coward" Wynne set out to make crossword puzzles of his own, and got nowhere. He was such a coward that every time he thought of a clever clue for a word, he could not stop worrying that people would blame him for picking a clue that could never mean that word. Day after day he gave in and chose a dull clue, so his puzzles came out flat.

One day he hit on a better idea: a puzzle where the meanings of the words do not matter at all, and which is still fun to solve. His colleagues agreed that the idea was interesting, and they named the format Coward's Crossword Puzzles after his nickname.

Making one was not easy. He no longer had to think about what the words meant, but checking that a puzzle has one and only one set of answers was still hard. With the anniversary approaching, John began to worry that he would not finish an interesting puzzle in time. Help John by writing a program that solves Coward's crossword puzzles.

A puzzle is a grid of h × w cells with h across clues and w down clues. The i-th across clue must match row i read from left to right, and the j-th down clue must match column j read from top to bottom. Every clue is a regular expression written in the pattern language whose BNF syntax is given below.

clue       ::= "^" pattern "$"
pattern    ::= simple | pattern "|" simple
simple     ::= basic | simple basic
basic      ::= elementary | elementary "*"
elementary ::= "." | "A" | "B" | ... | "Z" | "(" pattern ")"

BNF syntax of the pattern language.

Clues (p and q below) match words (s below) by the following rules.

• ^p$ matches s if p matches s.
• p|q matches s if p matches s, or q matches s, or both.
• pq matches s if there are s1 and s2 with s1s2 = s such that p matches s1 and q matches s2.
• p* matches s if s is empty, or if there are s1 and s2 with s1s2 = s such that p matches s1 and p* matches s2.
• Each of A, B, ..., Z matches that letter itself.
• (p) matches s if p matches s.
• . is the shorthand of (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).

The picture below is a Coward's crossword puzzle with the answers filled into the cells.

Java: a submitted Java program may not use the classes in the java.util.regex package.

C++: a submitted C++ program may not use the std::regex class.

Everyone in this problem except Arthur Wynne is fictitious. Any resemblance to real persons, living or dead, is coincidental.

The input has several datasets, each of which gives one puzzle in the following format.

h w
p1
p2
.
.
.
ph
q1
q2
.
.
.
qw

h and w are the vertical and horizontal numbers of cells, where 2 ≤ h, w ≤ 4. pi is the across clue for row i, and qj is the down clue for column j. No clue is longer than 512 characters.

A line of two zeros follows the last dataset. The input has at most 30 datasets.

For each dataset, when the puzzle has one and only one set of answers, print it as h lines of w characters. Print none when the puzzle has no set of answers, and ambiguous when it has more than one.