Problem Description

E869120 and square1001 had identical length "correct bracket sequences". A "correct bracket sequence" is defined as follows:

• () is a correct bracket sequence.
• If $ X $ is a correct bracket sequence, then (, $ X $, and ) concatenated in this order is also a correct bracket sequence.
• If $ X $ and $ Y $ are correct bracket sequences, then $ X $ and $ Y $ concatenated in this order is also a correct bracket sequence.
• Any other bracket sequence is incorrect.

Here, let the bracket sequence of E869120 be $ A $ and the bracket sequence of square1001 be $ B $. chokudai performed the following operations on $ A $ and $ B $:

• For each character in $ B $, if it is (, change it to ), and if it is ), change it to (. Then define a string $ C $ (initially an empty string) and repeat one of the following two operations until both $ A $ and $ B $ become empty strings:
• Insert the first character of $ A $ at the end of string $ C $, then delete the first character of $ A $.
• Insert the first character of $ B $ at the end of string $ C $, then delete the first character of $ B $.

Given a string $ S $, determine if it is possible for $ S $ to be equal to $ C $ and output Yes or No.

Input Format

The input is given from the standard input in the following format. Note that you must answer $ Q $ queries. For the $ i $-th query, $ S $ is denoted as $ S_i $.

$ Q $ $ S_1 $ $ S_2 $ : $ S_Q $

Output Format

Output $ Q $ lines.
The $ i $-th line should contain Yes or No indicating whether it is possible for $ S $ to be equal to $ C $ for the $ i $-th query.

Sample Input and Output

Sample Input #1

4
(())
)()(
(())
)(()

Sample Output #1

No
Yes
No
Yes

Sample Input #2

1
(())(()(

Sample Output #2

No

Sample Input #3

11
))(((()()())
))((())(())(
()())))(()((
)(()())()()(
)(())())(()(
)(()))()((()
)()()()())((
(())(()())()
)(())(()())(
((()())(()))
)))()())()()

Sample Output #3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

Notes/Hints

Constraints

• $ Q $ is an integer between $ 1 $ and $ 50 $ inclusive.
• $ S_i $ is a string consisting of ( and ) with a length between $ 1 $ and $ 20,000 $ inclusive.
• The length of $ S_i $ is a multiple of $ 4 $.

Subtasks

Subtask $ 1 $ \[$ 90 $ points\]

• Satisfies $|S| \leq 16$.

Subtask $ 2 $ \[$ 100 $ points\]

• Satisfies $|S| \leq 50$.

Subtask $ 3 $ \[$ 310 $ points\]

• No additional constraints.

Sample Explanation 1

For example, in the second query ($ S_2 $), if $ A $ = "()", $ B $ = ")(" and $ C $ is inserted in the order BAAB, then $ C $ = )()( can be achieved. The transitions of $ A $, $ B $, and $ C $ are as follows:
- $ A $ = "()", $ B $ = ")(", $ C $ = ""
- $ A $ = "()", $ B $ = "(", $ C $ = ")"
- $ A $ = ")", $ B $ = "(", $ C $ = ")("
- $ A $ = "", $ B $ = "(", $ C $ = ")()"
- $ A $ = "", $ B $ = "", $ C $ = ")()("

Sample Explanation 2

In this case, there are $ 5 $ ( and $ 3 $ ) characters. Since a correct bracket sequence must have an equal number of ( and ), it is impossible for $ S $ to be equal to $ C $.

见题面 Input 部分

见题面 Output 部分