#abc283d. [abc283_d]Scope

[abc283_d]Scope

Problem Statement

A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:

  • First, remove all lowercase English letters.
  • Then, repeatedly remove consecutive () while possible.

For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the 22-nd and 33-rd characters to obtain (), which in turn ends up in an empty string.

You are given a good string SS. We denote by SiS_i the ii-th character of SS.

For each lowercase English letter a, b, ldots\\ldots, and z, we have a ball with the letter written on it. Additionally, we have an empty box.

For each i=1,2,i = 1,2, ldots\\ldots ,S,|S| in this order, Takahashi performs the following operation unless he faints.

  • If SiS_i is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
  • If SiS_i is (, do nothing.
  • If SiS_i is ), take the maximum integer jj less than ii such that the jj-th through ii-th characters of SS form a good string. (We can prove that such an integer jj always exists.) Take out from the box all the balls that he has put in the jj-th through ii-th operations.

Determine if Takahashi can complete the sequence of operations without fainting.

Constraints

  • 1leqSleq3times1051 \\leq |S| \\leq 3 \\times 10^5
  • SS is a good string.

Input

The input is given from Standard Input in the following format:

SS

Output

Print Yes if he can complete the sequence of operations without fainting; print No otherwise.


Sample Input 1

((a)ba)

Sample Output 1

Yes

For i=1i = 1, he does nothing.
For i=2i = 2, he does nothing.
For i=3i = 3, he puts the ball with a written on it into the box.
For i=4i = 4, j=2j=2 is the maximum integer less than 44 such that the jj-th through 44-th characters of SS form a good string, so he takes out the ball with a written on it from the box.
For i=5i = 5, he puts the ball with b written on it into the box.
For i=6i = 6, he puts the ball with a written on it into the box.
For i=7i = 7, j=1j=1 is the maximum integer less than 77 such that the jj-th through 77-th characters of SS form a good string, so he takes out the ball with a written on it, and another with b, from the box.

Therefore, the answer to this case is Yes.


Sample Input 2

(a(ba))

Sample Output 2

No

For i=1i = 1, he does nothing.
For i=2i = 2, he puts the ball with a written on it into the box.
For i=3i = 3, he does nothing.
For i=4i = 4, he puts the ball with b written on it into the box.
For i=5i = 5, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.

Therefore, the answer to this case is No.


Sample Input 3

(((())))

Sample Output 3

Yes

Sample Input 4

abca

Sample Output 4

No