J. Juxtaposed brackets
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

递归定义集合$$$B$$$如下：

(1) $$$() \in B$$$

(2) 若 $$$x,y \in B$$$，则$$$(x),(xy) \in B$$$。

给定一个非空字符串 $$$S$$$，其中$$$S$$$只由两种字符"("和")"组成。

请你回答这个字符串是否属于$$$B$$$。

离散数学第3版第21页
Input

第一行一个整数$$$T$$$($$$1 \leq T \leq 3 \times 10^5$$$)表示数据组数。

接下来有 $$$T$$$ 行，每行有一个字符串$$$S$$$，含义见上。

在同一数据点内，我们保证$$$\sum |S| \leq 3 \times 10^5$$$。

保证字符串的所有字符只会是"(",")"。

Output

输出 $$$T$$$ 行，如果给定的字符串属于$$$B$$$，那么输出"YES"，否则输出"NO"。

Example
Input
5
((())())
(()())
()()
(()()))
((()())())
Output
YES
YES
NO
NO
YES
Note

这里展示了把用递归定义展开成原串的过程：

样例一解释：S->(SS)->((S)S)->((())S)->((())())。

样例二解释：S->(SS)->(()S)->(()())。

样例五解释：S->(SS)->((SS)S)->((()S)S)->((()())S)->((()())())。