题目描述

如果一个括号序列可以通过在其中插入字符 $+$ 和 $1$ 得到一个正确的算术表达式，则称该括号序列为“合法括号序列”（Regular Bracket Sequence，简称 RBS）。例如，序列 (())()、() 和 (()(())) 是合法的，而 )(、(() 和 (()))( 不是合法的。

现在给你一个长度为 $n$ 的序列 $s$，其中包含字符 (、) 和/或 ?。该序列中恰好有一个字符 ( 和一个字符 )。

你需要将每一个 ? 替换为 ) 或 (（不同的 ? 可以替换为不同的括号）。你不能改变字符的顺序，不能删除或插入其他字符，并且每个 ? 都必须被替换。

请判断，是否存在一种替换方式，使得替换后的序列是一个合法括号序列（RBS）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

每个测试用例包含一行，包含一个字符串 $s$（$2 \le |s| \le 100$），由字符 (、) 和/或 ? 组成。该序列中恰好有一个字符 ( 和一个字符 )。

输出格式

对于每个测试用例，如果存在一种替换方式使得序列成为合法括号序列，输出 YES，否则输出 NO。

你可以用任意大小写输出答案（例如，YES、Yes、yes、yEs 都会被识别为正确答案）。

说明/提示

在第一个测试用例中，序列已经是一个合法括号序列。

在第三个测试用例中，你可以将其替换为 ()() 或 (())，从而得到合法括号序列。

在第四个测试用例中，你可以将其替换为 ()()，从而得到合法括号序列。

由 ChatGPT 4.1 翻译

样例

5
()
(?)
(??)
??()
)?(?

YES
NO
YES
YES
NO