如果可以通过添加字符“+”和“1”将括号序列变成有效的数学表达式,则该括号序列称为平衡的。例如,序列 '(())()'、'()' 和 '(()(()))' 是平衡的,而 ')('、'(()' 和 '(()))(' 不是平衡的。
给你一个长度为$$$n$$$的二进制字符串$$$s$$$。构造两个长度为 $$$n$$$ 的平衡括号序列 $$$a$$$ 和 $$$b$$$,使得对于所有 $$$1\le i\le n$$$:
- 如果 $$$s_i=1$$$,则 $$$a_i=b_i$$$
- 如果 $$$s_i=0$$$,则 $$$a_i\ne b_i$$$
如果不可能,您应该报告。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$,$$$n$$$ 是偶数)。
下一行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0 和 1 组成。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
如果存在这样的两个平衡括号序列,则在第一行输出“YES”,否则输出“NO”。您可以以任何大小写(大写或小写)打印每个字母。
如果答案为“YES”,则在接下来的两行输出满足条件的平衡括号序列$$$a$$$和$$$b$$$。
如果有多个解决方案,您可以打印任何一个。
示例
输入 #1
3 6 101101 10 1001101101 4 1100
输出 #1
YES ()()() ((())) YES ()()((())) (())()()() NO
注意
在第一个测试用例中,$$$a=$$$"()()()" 和 $$$b=$$$"((()))"。 $$$1$$$、$$$3$$$、$$$4$$$ 和 $$$6$$$ 位置上的字符相等,这些位置与 $$$s_i=1$$$ 的位置完全相同。
在第二个测试用例中,$$$a=$$$"()()((()))" 和 $$$b=$$$"(())()()()"。 $$$1$$$、$$$4$$$、$$$5$$$、$$$7$$$、$$$8$$$、$$$10$$$ 中的字符是相等的,它们与 $$$s_i=1$$$ 的位置完全相同。
在第三个测试用例中,没有解决方案。