CF1896F.Bracket Xoring

You are given a binary string $s$ of length $2n$ where each element is $\mathtt{0}$ or $\mathtt{1}$. You can do the following operation:

1. Choose a balanced bracket sequence$^\dagger$ $b$ of length $2n$.
2. For every index $i$ from $1$ to $2n$ in order, where $b_i$ is an open bracket, let $p_i$ denote the minimum index such that $b[i,p_i]$ is a balanced bracket sequence. Then, we perform a range toggle operation$^\ddagger$ from $i$ to $p_i$ on $s$. Note that since a balanced bracket sequence of length $2n$ will have $n$ open brackets, we will do $n$ range toggle operations on $s$.

Your task is to find a sequence of no more than $10$ operations that changes all elements of $s$ to $\mathtt{0}$, or determine that it is impossible to do so. Note that you do not have to minimize the number of operations.

Under the given constraints, it can be proven that if it is possible to change all elements of $s$ to $\mathtt{0}$, there exists a way that requires no more than $10$ operations.

$^\dagger$ 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.

$^\ddagger$ If we perform a range toggle operation from $l$ to $r$ on a binary string $s$, then we toggle all values of $s_i$ such that $l \leq i \leq r$. If $s_i$ is toggled, we will set $s_i := \mathtt{0}$ if $s_i = \mathtt{1}$ or vice versa. For example, if $s=\mathtt{1000101}$ and we perform a range toggle operation from $3$ to $5$, $s$ will be changed to $s=\mathtt{1011001}$.

给你一个长度为 $2n$ 的二进制字符串 $s$，其中每个元素为 $\mathtt{0}$ 或 $\mathtt{1}$。你可以执行以下操作：

1. 选择一个长度为 $2n$ 的平衡括号序列$^\dagger$ $b$。
2. 按照从 $1$ 到 $2n$ 的顺序，对每个满足 $b_i$ 是左括号的下标 $i$，令 $p_i$ 表示满足子串 $b[i,p_i]$ 构成平衡括号序列的最小下标。接着，我们在 $s$ 上执行一次从 $i$ 到 $p_i$ 的区间翻转操作$^\ddagger$。注意：由于长度为 $2n$ 的平衡括号序列恰好包含 $n$ 个左括号，因此该操作总共会对 $s$ 执行 $n$ 次区间翻转。

你的任务是：找到至多 $10$ 次操作的序列，使得 $s$ 的所有元素均变为 $\mathtt{0}$；若无法实现，则判定其不可能。注意：你无需最小化操作次数。

在本题给定的约束条件下，可以证明：若能将 $s$ 全部变为 $\mathtt{0}$，则一定存在一种方案，其操作次数不超过 $10$ 次。

$^\dagger$ 若一个括号序列可通过添加字符 $+$ 和 $1$ 变为合法的数学表达式，则称其为平衡括号序列。例如，"(())()"、"()" 和 "(()(()))" 是平衡的，而 ")("、"(()" 和 "(()))(" 不是。

$^\ddagger$ 对二进制字符串 $s$ 执行从 $l$ 到 $r$ 的区间翻转操作，指将所有满足 $l \leq i \leq r$ 的 $s_i$ 进行翻转：若 $s_i = \mathtt{1}$，则设为 $\mathtt{0}$；若 $s_i = \mathtt{0}$，则设为 $\mathtt{1}$。例如，若 $s=\mathtt{1000101}$，执行从 $3$ 到 $5$ 的区间翻转后，$s$ 将变为 $\mathtt{1011001}$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — where $2n$ is the length of string $s$.

The second line of each test case contains a binary string $s$ of length $2n$ ($s_i = \mathtt{0}$ or $s_i = \mathtt{1}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），其中 $2n$ 是字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $2n$ 的二进制字符串 $s$（即对所有 $i$，有 $s_i = \mathtt{0}$ 或 $s_i = \mathtt{1}$）。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, output $-1$ in a single line if it is impossible to change all elements of $s$ to $\mathtt{0}$.

Otherwise, output a single integer $k$ ($0 \le k \le 10$) representing the number of operations needed to change all elements of $s$ to $\mathtt{0}$. Then, on each of the next $k$ lines, output a balanced bracket sequence of length $2n$ representing the operations needed to change all elements of $s$ to $0$s.

If there are multiple ways to change all elements of $s$ to $\mathtt{0}$ that require not more than $10$ operations, you can output any of them.

对于每个测试用例，如果无法将字符串 $s$ 的所有元素都变为 $\mathtt{0}$，则在一行中输出 $-1$。

否则，输出一个整数 $k$（$0 \le k \le 10$），表示将 $s$ 的所有元素变为 $\mathtt{0}$ 所需的操作次数。随后的 $k$ 行中，每行输出一个长度为 $2n$ 的平衡括号序列，表示将 $s$ 的所有元素变为 $\mathtt{0}$ 所需的操作。

若存在多种方案可在不超过 $10$ 次操作内将 $s$ 的所有元素变为 $\mathtt{0}$，则输出任意一种即可。

In the first test case, it can be proven that it is impossible to change all elements of $s$ to $\mathtt{0}$.

In the second test case, the first operation using the bracket sequence $b = \mathtt{()()}$ will convert the binary string $s=\mathtt{0000}$ to $s=\mathtt{1111}$. Then, the second operation using the same bracket sequence $b = \mathtt{()()}$ will convert the binary string $s=\mathtt{1111}$ back to $s=\mathtt{0000}$. Note that since all elements of $s$ is already $\mathtt{0}$ initially, using $0$ operations is also a valid answer.

In the third test case, a single operation using the bracket sequence $b = \mathtt{(())()}$ will change all elements of $s$ to $\mathtt{0}$. The operation will happen as follows.

1. $b_1$ is an open bracket and $p_1 = 4$ since $b[1,4]=\mathtt{(())}$ is a balanced bracket sequence. Hence, we do a range toggle operation from $1$ to $4$ on the binary string $s = \mathtt{100111}$ to obtain $s = \mathtt{011011}$.
2. $b_2$ is an open bracket and $p_2 = 3$ since $b[2,3]=\mathtt{()}$ is a balanced bracket sequence. Hence, we do a range toggle operation from $2$ to $3$ on the binary string $s = \mathtt{011011}$ to obtain $s = \mathtt{000011}$.
3. $b_3$ is not an open bracket, so no range toggle operation is done at this step.
4. $b_4$ is not an open bracket, so no range toggle operation is done at this step.
5. $b_5$ is an open bracket and $p_5 = 6$ since $b[5,6]=\mathtt{()}$ is a balanced bracket sequence. Hence, we do a range toggle operation from $5$ to $6$ on the binary string $s = \mathtt{000011}$ to obtain $s = \mathtt{000000}$.
6. $b_6$ is not an open bracket, so no range toggle operation is done at this step.

In the fourth test case, the first operation using the bracket sequence $b = \mathtt{(((())))}$ will convert the binary string $s = \mathtt{01011100}$ to $s = \mathtt{11111001}$. Then, the second operation using the bracket sequence $b = \mathtt{()()(())}$ will convert the binary string $s = \mathtt{11111001}$ to $s=\mathtt{00000000}$.

在第一个测试用例中，可以证明无法将 $s$ 的所有元素都变为 $\mathtt{0}$。

在第二个测试用例中，第一次操作使用括号序列 $b = \mathtt{()()}$，将二进制字符串 $s=\mathtt{0000}$ 转换为 $s=\mathtt{1111}$；随后，第二次操作再次使用相同的括号序列 $b = \mathtt{()()}$，将二进制字符串 $s=\mathtt{1111}$ 恢复为 $s=\mathtt{0000}$。注意：由于 $s$ 初始时所有元素已是 $\mathtt{0}$，因此执行 $0$ 次操作也是一个合法答案。

在第三个测试用例中，仅需一次操作，使用括号序列 $b = \mathtt{(())()}$ 即可将 $s$ 的所有元素变为 $\mathtt{0}$。该操作过程如下：

1. $b_1$ 是左括号，且 $p_1 = 4$（因为子串 $b[1,4]=\mathtt{(())}$ 是一个平衡括号序列），因此对二进制字符串 $s = \mathtt{100111}$ 执行区间翻转操作 $[1,4]$，得到 $s = \mathtt{011011}$。
2. $b_2$ 是左括号，且 $p_2 = 3$（因为子串 $b[2,3]=\mathtt{()}$ 是一个平衡括号序列），因此对二进制字符串 $s = \mathtt{011011}$ 执行区间翻转操作 $[2,3]$，得到 $s = \mathtt{000011}$。
3. $b_3$ 不是左括号，因此此步不执行任何区间翻转操作。
4. $b_4$ 不是左括号，因此此步不执行任何区间翻转操作。
5. $b_5$ 是左括号，且 $p_5 = 6$（因为子串 $b[5,6]=\mathtt{()}$ 是一个平衡括号序列），因此对二进制字符串 $s = \mathtt{000011}$ 执行区间翻转操作 $[5,6]$，得到 $s = \mathtt{000000}$。
6. $b_6$ 不是左括号，因此此步不执行任何区间翻转操作。

在第四个测试用例中，第一次操作使用括号序列 $b = \mathtt{(((())))}$，将二进制字符串 $s = \mathtt{01011100}$ 转换为 $s = \mathtt{11111001}$；随后，第二次操作使用括号序列 $b = \mathtt{()()(())}$，将二进制字符串 $s = \mathtt{11111001}$ 转换为 $s=\mathtt{00000000}$。