CF1503A.Balance the Bits

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

You are given a binary string $s$ of length $n$. Construct two balanced bracket sequences $a$ and $b$ of length $n$ such that for all $1\le i\le n$:

• if $s_i=1$, then $a_i=b_i$
• if $s_i=0$, then $a_i\ne b_i$

If it is impossible, you should report about it.

如果可以通过添加字符 '+' 和 '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$。

若无法构造，应报告该情况。

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$, $n$ is even).

The next line contains a string $s$ of length $n$, consisting of characters 0 and 1.

The sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $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$。

If such two balanced bracked sequences exist, output "YES" on the first line, otherwise output "NO". You can print each letter in any case (upper or lower).

If the answer is "YES", output the balanced bracket sequences $a$ and $b$ satisfying the conditions on the next two lines.

If there are multiple solutions, you may print any.

如果存在这样两个平衡括号序列，则在第一行输出 "YES"；否则输出 "NO"。每个字母可使用大写或小写形式。

如果答案为 "YES"，则在接下来的两行中分别输出满足条件的平衡括号序列 $a$ 和 $b$。

若存在多种解，输出任意一种即可。

In the first test case, $a=$"()()()" and $b=$"((()))". The characters are equal in positions $1$, $3$, $4$, and $6$, which are the exact same positions where $s_i=1$.

In the second test case, $a=$"()()((()))" and $b=$"(())()()()". The characters are equal in positions $1$, $4$, $5$, $7$, $8$, $10$, which are the exact same positions where $s_i=1$.

In the third test case, there is no solution.

在第一个测试用例中，$a=$"()()()" 且 $b=$"((()))"。字符在位置 $1$、$3$、$4$ 和 $6$ 处相等，这些位置恰好与 $s_i=1$ 的位置完全一致。

在第二个测试用例中，$a=$"()()((()))" 且 $b=$"(())()()()"。字符在位置 $1$、$4$、$5$、$7$、$8$、$10$ 处相等，这些位置恰好与 $s_i=1$ 的位置完全一致。

在第三个测试用例中，无解。