括号序列是由字符“(”和/或“)”组成的字符串。常规括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:
- 括号序列“()()”和“(())”是规则的(它们可以分别转化为“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不规则。
给你一个括号序列$$$s$$$;让我们将其长度定义为$$$n$$$。您的任务是找到长度为 $$$2n$$$ 的常规括号序列 $$$t$$$,使得 $$$s$$$ 不会作为连续子字符串出现在 $$$t$$$ 中,或者报告不存在这样的序列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 50$$$),由字符“(”和/或“)”组成。
输出
对于每个测试用例,打印其答案。如果没有需要的常规括号序列,则在单独的行中打印“NO”。否则,在第一行中打印 YES,并在第二行中打印所需的常规括号序列 $$$t$$$ 本身。如果有多个答案 - 您可以打印其中任何一个。
示例
输入 #1
4 )( (() () ))()
输出 #1
YES (()) YES ()()() NO YES ()(()())