UVA1672 不相交的正规表达式 Disjoint Regular Expressions

Mark 正在为“火卫一”（Phobos）和“火卫二”（Deimos）的居民开发一个新的社交网络 Facepalm。他最近的任务是在每一个帐户中添加关于用户所居住的卫星的信息。当然，每个帐户所有者都可以输入这样的信息，但是Mark决定，如果在登录时给用户填上一些默认值，会更方便一些。 她对这一情况进行了调查，发现用户的姓氏可以用来分析她们所居住的卫星。Facepalm 的每个用户的姓氏是一个非空单词，由英文字母的小写字母组成。 “火卫一”（Phobos）用户的姓氏全部与正则表达式 P 匹配，而“火卫二”（Deimos）用户的姓氏与表达式 D 匹配。我们定义，如果没有能够同时匹配两个表达式的非空字符串 S，则认为两个表达式不相交。 Mark 认为 P 和 D 的是不相交的，但是她需要你帮她检查这个结论。您将得到两个正则表达式 P 和 D。请检查它们是否不相交，如果相交，则查找匹配它们的最短的非空字符串。如果有多个个最短的公共字符串，您找到任何一个都是可以的。 #### 正则表达式和匹配字符串的形式化定义 - 单个小写字母 c 是一个正则表达式，它只匹配一个由单个字母 c 组成的字符串。 - 交替（Alternation）：如果 P 和 Q 是正则表达式，那么 `(P|Q)` 是一个正则表达式。对于字符串 $\alpha$,如果 $\alpha$ 匹配 P 或者是 $\alpha$ 匹配 Q，那么 $\alpha$ 就匹配 `(P|Q)`。 - 级联（Concatenation）：如果 P 和 Q 是正则表达式，那么 `(PQ)` 是一个正则表达式.对于字符串 $\alpha$,如果 $\alpha=\beta+\gamma$（这里 $+$ 表示字符串拼接），且 $\beta$ 匹配 P、$\gamma$ 匹配 Q，那么 $\alpha$ 就匹配 `(PQ)`。 - 闭包（Kleene star / Kleene ）：如果 P 是一个正则表达式，那么 `P*` 是一个正则表达式。对于字符串 $\alpha$，如果 $\alpha=\alpha_1\alpha_2\cdots\alpha_k$ 且 $\alpha_1$、$\alpha_2$、$\cdots$、$\alpha_k$ 均匹配 P，则 $\alpha$ 匹配 `P*` 上文中的括号可以被省略。如果被省略，则闭包（Kleene star）具有最高的优先级，然后是级联（Concatenation），然后是交替（Alternation）。例如，`abc*|de` 表示 `(ab(c*))|(de)`。

输入将包含若干测试样例，每个测试样例包含两行。第一行为正则表达式 P，第二行为正则表达式 D。每个表达式包含 1 到 100 个字符。

对于每个测试样例，如果Mark的猜测是正确的（即这两个表达式确实是不相交的）那么输出 `Correct`。否则，第一行输出 `Wrong`，第二行输出同时匹配两个表达式的任何最短的非空字符串。