括号序列是仅包含字符“(”和“)”的字符串。常规括号序列(或者简称为 RBS)是可以通过在序列的原始字符之间插入字符“1”和“+”来转换为正确的算术表达式的括号序列。例如:
- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。
有苏格兰皇家银行。一些括号已替换为问号。是否真的有一种独特的方法可以用括号替换问号,从而得到的序列是 RBS?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个 RBS,其中一些括号替换为问号。每个字符都是“(”、“)”或“?”。可以从给定序列中恢复至少一个RBS。
所有测试用例的序列总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果用括号替换问号(以便生成的序列是 RBS)的方式是唯一的,则打印“YES”。如果有不止一种方式,则打印“NO”。
示例
输入 #1
5 (?)) ?????? () ?? ?(?)()?)
输出 #1
YES NO YES YES NO
注意
在第一个测试用例中,唯一可能的原始 RBS 是“(())”。
在第二个测试用例中,有多种方法可以恢复 RBS。
在第三个和第四个测试用例中,唯一可能的原始 RBS 是“()”。
在第五个测试用例中,原始 RBS 可以是“((()()))”或“(())()()”。