Regular Bracket Sequence
Contest: Educational Codeforces Round 101 (Rated for Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters + and 1 into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence "RBS".

You are given a sequence $$$s$$$ of $$$n$$$ characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

You have to replace every character ? with either ) or ( (different characters ? can be replaced with different brackets). You cannot reorder the characters, remove them, insert other characters, and each ? must be replaced.

Determine if it is possible to obtain an RBS after these replacements.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of one line containing $$$s$$$ ($$$2 \le |s| \le 100$$$) — a sequence of characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

Output format:
For each test case, print YES if it is possible to obtain a regular bracket sequence, or NO otherwise}.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the sequence is already an RBS.

In the third test case, you can obtain an RBS as follows: ()() or (()).

In the fourth test case, you can obtain an RBS as follows: ()().

Example input:
5
()
(?)
(??)
??()
)?(?

Example output:
YES
NO
YES
YES
NO

Editorial:
There are two solutions to this problem: casework and greedy.
The greedy solution goes as follows: the number of opening brackets in an RBS should be exactly $$$\frac{|s|}{2}$$$, and if there is a closing bracket before an opening bracket, it's optimal to swap them, if possible. So, we should replace the first $$$\frac{|s|}{2} - 1$$$ question marks with opening brackets, other question marks with closing brackets, and if the answer exists, this method will find it. All that's left is to check that the resulting sequence is an RBS.
The casework solution goes as follows: first of all, each RBS should have an even length, so if $$$|s|$$$ is odd, there is no answer. Furthermore, an RBS always begins with an opening bracket and always ends with a closing bracket, so if the first character is a closing bracket or the last character is an opening bracket, there is no answer. Since there is at most one opening bracket and at most one closing bracket in the original sequence, these three constraints are enough: if the opening bracket is before the closing bracket, then they balance out, and all other characters can be replaced in such a way that they form an RBS of length $$$|s| - 2$$$. If the opening bracket is after the closing bracket, then the first and the last characters are question marks (since the first character is not a closing bracket, and the last one is not an opening bracket). We should replace the first character with an opening bracket, the last character with a closing bracket, so we get four characters (two opening and two closing brackets) which balance themselves out. All other question marks can be replaced in such a way that they form an RBS of length $$$|s| - 4$$$. So, all we have to check is that $$$|s|$$$ is even, the first character is not a closing bracket, and the last character is not an opening bracket.