問題文

ここでは、以下の構文で表される文字列を "正規表現" と呼ぶ。

e ::= a...a | (e_1+e_2) | (e_1;e_2) | *(e_1) | !(e_1)

ただし、a...a は 文字 a の 1 回以上の繰り返しによって表せるようなある文字列を表す。

正規表現 e が表現する文字列の集合 L(e) は以下で帰納的に定義される。

L(a...a) = \{a...a\}
       - 例えば、L(aa) = \{aa\}, L(aaa) = \{aaa\}。
L((e_1+e_2)) = L(e_1) ∪ L(e_2)
       - L(e_1) に属する または L(e_2) に属する 文字列 の集合。
L((e_1;e_2)) = L(e_1)L(e_2) = \{ w_1 w_2 | w_1 \in L(e_1), w_2 \in L(e_2) \}
       - L(e_1) に属する文字列 と L(e_2) に属する文字列 をつなげた文字列の集合。
L(*(e_1)) = L(e_1)^* = \{ε\} ∪ \{w_1 | w_1 \in L(e_1)\} ∪ ... ∪ \{w_1 ... w_n | w_1,...,w_n \in L(e_1)\} ∪ ...
       - L(e_1) に属する文字列 を 有限回つなげた (0 回の場合も含む) 文字列の集合。
L(!(e_1)) = Σ^* - L(e_1)
       - L(e_1) に属さない文字列 の集合。

ただし、Σ^* は文字列の全体集合 \{ε(空の文字列),a,aa,aaa,...\} = ( a を有限個つなげた文字列の集合) を表す。

また、以下の文中で"!なし正規表現" とは ! が出現しない 正規表現 を指し、 "*なし正規表現" とは * が出現しない 正規表現 を指します。

さて、!なし正規表現 S が与えられます。

L(S) = L(T) を満たす *なし正規表現 T が存在するかどうか判定してください。

入力例1

6
(a+aa)

出力例1

YES

T = (a+aa) とすればよい。

入力例2

17
(*(aa)+(*(aa);a))

出力例2

YES

T = (!(a)+a) とすればよい。

入力例3

14
(*(aa)+*(aaa))

出力例3

NO

L(S) = L(T) を満たす *なし正規表現 T は存在しません。