题目描述

括号序列是仅由字符“(”和/或“)”组成的字符串。一个合法括号序列是指可以通过在原序列的字符之间插入字符“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$。如果有多种答案，可以输出任意一种。

说明/提示

由 ChatGPT 4.1 翻译

样例

4
)(
(()
()
))()

YES
(())
YES
()()()
NO
YES
()(()())