CF1860A Not a Substring

括号序列是仅由字符“(”和/或“)”组成的字符串。一个合法括号序列是指可以通过在原序列的字符之间插入字符“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 翻译