第一个填字游戏由 Arthur Wynne 于 1913 年 12 月 21 日发表。为了庆祝他曾曾祖父的发明一百周年，John “Coward” Wynne 正在努力制作填字游戏。他非常胆小，每当他为一个单词想到一个棘手的线索时，他就会担心人们会因为他选择了一个永远无法代表该单词的糟糕线索而责怪他。最终，他胆怯地选择了无聊的线索，这使得他的谜题变得不那么有趣。

有一天，他想出了一个绝妙的主意：单词含义无关紧要，但依然有趣的谜题。他把这个想法告诉了他的同事，他们承认这个想法很有趣。他们甚至以他的绰号将他的谜题命名为“Coward’s Crossword Puzzles”。

然而，制作“Coward’s Crossword Puzzles”并不容易。即使他不必考虑单词的含义，也很难检查一个谜题是否只有唯一的一组答案。随着百年纪念日的临近，John 开始担心他是否无法及时做出有趣的谜题。让我们通过编写一个程序来解决“Coward’s Crossword Puzzles”来帮助 John。

每个谜题由 $h \times w$ 个单元格组成，以及 $h$ 个横向线索和 $w$ 个纵向线索。线索是用一种模式语言编写的正则表达式，其 BNF 语法如下表所示。

表 J.1. 模式语言的 BNF 语法。

线索（下文用 $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 特别说明：提交的 Java 程序不得使用 java.util.regex 包中的类。 C++ 特别说明：提交的 C++ 程序不得使用 std::regex 类。

输入格式

输入包含多个数据集，每个数据集代表一个谜题，格式如下：

$h \ w$ $p_1$ $p_2$ $\vdots$ $p_h$ $q_1$ $q_2$ $\vdots$ $q_w$

其中 $h$ 和 $w$ 分别表示单元格的行数和列数，满足 $2 \le h, w \le 4$。$p_i$ 和 $q_j$ 分别是第 $i$ 行的横向线索和第 $j$ 列的纵向线索。任何线索的长度不超过 512 个字符。

最后一个数据集后面跟着一行两个零。你可以假设输入中不超过 30 个数据集。

输出格式

对于每个数据集，如果谜题有唯一的一组答案，则将其输出为 $h$ 行，每行 $w$ 个字符。如果谜题没有答案，或者有多于一组的答案，则分别输出 “none” 或 “ambiguous”（不含双引号）。

样例

样例输入 1

2 2
^(C|I|T|Y)*$
^(C|O|P|S)*$
^(F|L|I|P)*$
^(B|A|C|K)*$
2 2
^HE|LL|O*$
^(P|L|E|A|S|E)*$
^(H|L)*$
^EP|IP|EF$
4 4
^LONG|TALL|S*ALLY$
^(R*EV*|OL*U(TIO)*N)*$
^(STRAWBERRY|F*I*E*L*D*S*|FOREVER)*$
^P.S.|I|LOVE|YOU$
^(RE|A|L)((L|OV*E)*)$
^(LUC*Y*|IN.THE.SKY)(WITH|DI*A*M*ON*D*S*)$
^(IVE*|GOT|A|F*E*E*L*I*N*G*)*$
^YEST*E*R*D*A*Y*$
2 3
^(C|P)(OL|AS)$
^(LU|TO)(X|R)$
^CT|PL$
^OU|AO$
^SR|LX$
2 2
^T*|(HI)|S*$
^SE|NT|EN|CE$
^IS$
^(F|A|L|S|E)*$
2 4
^ARKA|BARB|COLU$
^NSAS|ADOS|MBIA$
^..$
^..$
^KA|RO|LI$
^AS|BA|US$
0 0

样例输出 1

IC
PC
HE
LP
ALLY
OUNE
EDIS
LOVE
ambiguous
none
ARKA
NSAS