给定一个长度为 $$$2n$$$ 的二进制字符串 $$$s$$$,其中每个元素为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$。您可以进行以下操作:
1. 选择长度为 $$$2n$$$ 的平衡括号序列$$$^\dagger$$$ $$$b$$$。
2. 对于按顺序从 $$$1$$$ 到 $$$2n$$$ 的每个索引 $$$i$$$,其中 $$$b_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$$$ 的范围切换操作,则我们切换 $$$s_i$$$ 的所有值,使得 $$$l \leq i \leq r$$$。如果 $$$s_i$$$ 被切换,如果 $$$s_i = \mathtt{1}$$$,我们将设置 $$$s_i := \mathtt{0}$$$,反之亦然。例如,如果 $$$s=\mathtt{1000101}$$$ 并且我们执行从 $$$3$$$ 到 $$$5$$$ 的范围切换操作,$$$s$$$ 将更改为 $$$s=\mathtt{1011001}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 其中 $$$2n$$$ 是字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$2n$$$ 的二进制字符串 $$$s$$$ ($$$s_i = \mathtt{0}$$$ 或 $$$s_i = \mathtt{1}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果不可能将 $$$s$$$ 的所有元素更改为 $$$\mathtt{0}$$$,则在一行中输出 $$$-1$$$。
否则,输出一个整数 $$$k$$$ ($$$0 \le k \le 10$$$),表示将 $$$s$$$ 的所有元素更改为 $$$\mathtt{0}$$$ 所需的操作数。然后,在接下来的 $$$k$$$ 行中,输出长度为 $$$2n$$$ 的平衡括号序列,表示将 $$$s$$$ 的所有元素更改为 $$$0$$$s 所需的操作。
如果有多种方法可以将 $$$s$$$ 的所有元素更改为 $$$\mathtt{0}$$$,并且需要不超过 $$$10$$$ 运算,则可以输出其中任何一个。
示例
输入 #1
4 1 01 2 0000 3 100111 4 01011100
输出 #1
-1 2 ()() ()() 1 (())() 2 (((()))) ()()(())
注意
在第一个测试用例中,可以证明不可能将$$$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}$$$。