配点 : $400$ 点

問題文

英小文字、(、) からなる文字列のうち、以下の手順によって空文字列になるものを良い文字列と呼びます:

• まず、英小文字をすべて削除する。
• 次に、連続する () が存在する限り、それを削除する。

例えば、((a)ba) は英小文字をすべて削除すると (()) となり、$2$ 文字目と $3$ 文字目に連続する () を削除すると () となり、最終的に空文字列にすることができるので良い文字列です。

良い文字列 $S$ が与えられます。 $S$ の $i$ 文字目を $S_i$ で表します。

各英小文字 a , b , $\ldots$ , z に対して、その文字が書かれたボールが $1$ つあります。 また、空の箱があります。

高橋君は $i = 1,2,$ $\ldots$ $,|S|$ に対してこの順に気を失わない限り操作を行います。

• $S_i$ が英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
• $S_i$ が ( ならば、何もしない。
• $S_i$ が ) ならば、$i$ 未満の整数 $j$ であって、$S$ の $j$ 番目から $i$ 番目までの文字からなる文字列が良い文字列となる最大の整数 $j$ を取る。（このような整数 $j$ は必ず存在することが証明できる。）$j$ 番目から $i$ 番目までの操作で箱に入れたボールをすべて、箱から取り出す。

高橋君が気を失わずに一連の操作を完了させられるか判定してください。

制約

• $1 \leq |S| \leq 3 \times 10^5$
• $S$ は良い文字列

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

高橋君が気を失わずに一連の操作を完了させられる場合は Yes を、そうでない場合は No を出力せよ。

((a)ba)

Yes

$i = 1$ のとき、高橋君は何もしません。 $i = 2$ のとき、高橋君は何もしません。 $i = 3$ のとき、高橋君は a の書かれたボールを箱の中に入れます。 $i = 4$ のとき、$4$ 未満の整数 $j$ であって、$S$ の $j$ 番目から $4$ 番目までの文字からなる文字列が良い文字列となる最大の整数は $2$ であるため、高橋君は a の書かれたボールを箱から取り出します。 $i = 5$ のとき、高橋君は b の書かれたボールを箱の中に入れます。 $i = 6$ のとき、高橋君は a の書かれたボールを箱の中に入れます。 $i = 7$ のとき、$7$ 未満の整数 $j$ であって、$S$ の $j$ 番目から $7$ 番目までの文字からなる文字列が良い文字列となる最大の整数は $1$ であるため、高橋君は a の書かれたボールと b の書かれたボールを箱から取り出します。

したがってこの場合の答えは Yes となります。

(a(ba))

No

$i = 1$ のとき、高橋君は何もしません。 $i = 2$ のとき、高橋君は a の書かれたボールを箱の中に入れます。 $i = 3$ のとき、高橋君は何もしません。 $i = 4$ のとき、高橋君は b の書かれたボールを箱の中に入れます。 $i = 5$ のとき、a の書かれたボールはすでに箱に入っているため、高橋君は気を失い、これ以降の操作は行われません。

したがってこの場合の答えは No となります。

(((())))

Yes

abca

No