题目描述

在计算机科学中，正则表达式是一种用于文本搜索和字符串匹配的强大工具。在本题中，我们使用一种简化版的正则表达式。

正则表达式及其匹配规则定义如下：

• 空字符串 $\varepsilon$ 是一个正则表达式，只有空字符串与它匹配。

• 单个小写字母：对于任意小写英文字母 $c$，字符 c 是一个正则表达式，并且只有仅由字符 $c$ 组成的长度为 $1$ 的字符串与它匹配。

• 点号：. 是一个正则表达式，任意由单个小写英文字母组成的字符串都与它匹配。

• 或运算：如果 $\alpha$ 和 $\beta$ 是正则表达式，那么

  $$(\alpha\mid\beta)$$

  也是一个正则表达式。当且仅当字符串 $s$ 匹配 $\alpha$ 或匹配 $\beta$ 时，$s$ 匹配 $(\alpha\mid\beta)$。

• 连接运算：如果 $\alpha$ 和 $\beta$ 是正则表达式，那么

  $$(\alpha\beta)$$

  也是一个正则表达式。当且仅当存在两个字符串 $x,y$，满足

  $$s=xy,$$

  且 $x$ 匹配 $\alpha$、$y$ 匹配 $\beta$ 时，字符串 $s$ 匹配 $(\alpha\beta)$。

• Kleene 星号：如果 $\alpha$ 是一个正则表达式，那么

  $$(\alpha^*)$$

  也是一个正则表达式。

  当且仅当满足下列条件之一时，字符串 $s$ 匹配 $(\alpha^*)$：

  1. $s=\varepsilon$，即 $s$ 是空字符串；
  2. 存在字符串 $x,y$，使得$$s=xy,$$ 其中 $x$ 非空且匹配 $\alpha$，而 $y$ 匹配 $(\alpha^*)$。

  换句话说，匹配 $(\alpha^*)$ 的字符串可以表示为

  $$s=x_1x_2\cdots x_k,\qquad k\ge 0,$$

  其中每个 $x_i$ 都匹配 $\alpha$。当 $k=0$ 时，$s$ 为空字符串。

括号可以根据运算优先级省略。在本题中，各运算符的优先级从高到低依次为：

1. Kleene 星号 *；
2. 连接运算；
3. 或运算 |。

因此，正则表达式

abc*|de

等价于

(ab(c*))|(de)

例如，字符串

abcabcab

匹配正则表达式

a(bc|a)*ab

而字符串

abcbab

不匹配该正则表达式。

你的任务是：找到一个长度最短的字符串 $T$，使得：

1. $T$ 匹配给定的正则表达式 $E$；
2. 给定字符串 $S$ 是 $T$ 的一个子串。

输入格式

输入共两行。

第一行包含一个正则表达式 $E$。

第二行包含一个字符串 $S$。

满足：

字符串 $S$ 仅由小写英文字母组成。

正则表达式 $E$ 仅由以下字符组成：

• 小写英文字母 a～z；
• 点号 .；
• 左右括号 (、)；
• 或运算符 |；
• Kleene 星号 *。

输出格式

如果存在满足条件的字符串，则输出一个长度最短的字符串 $T$，满足：

• $T$ 匹配正则表达式 $E$；
• $S$ 是 $T$ 的一个子串。

如果不存在这样的字符串，输出：

NO

字符串 $T$ 只能包含小写英文字母。

输入输出样例 #1

输入 #1

a.*b
bab

输出 #1

abab

输入输出样例 #2

输入 #2

(ab)*
bb

输出 #2

NO