给您一个长度为 $$$n$$$ 的方括号字符串 $$$s$$$。您可以按任意顺序任意次数(可能为零)应用以下操作:
- 选择索引 $$$1 \leq i \lt |s|$$$ 使得 $$$s_i = s_{i+1} = \texttt{(}$$$,并将 $$$s_i$$$ 和 $$$s_{i+1}$$$ 替换为 $$$\texttt{)}$$$。
- 选择索引 $$$1 \leq i \lt |s|$$$ 使得 $$$s_i = s_{i+1} = \texttt{)}$$$,并将 $$$s_i$$$ 和 $$$s_{i+1}$$$ 替换为 $$$\texttt{(}$$$。
找到一个规则的括号序列$$$^{\text{*}}$$$ $$$t$$$,它可以通过应用上述操作从$$$s$$$获得,如果没有这样的$$$t$$$,则打印$$$-1$$$。
$$$^{\text{*}}$$$正则括号序列是可以通过插入字符将括号序列转化为正确的算术表达式 "1" 和 "+" 序列的原始字符之间。例如:括号序列 "()()" 和 "(())" 是正则表达式(结果表达式是: "(1)+(1)" 和 "((1+1)+1)");括号序列 ")(", "(" 和 ")" 不是。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 字符串的长度。
第二行包含单个字符串 $$$s$$$ — 字符序列 ( 和 ) 长度为 $$$n$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个常规括号字符串 $$$t$$$,它可以从 $$$s$$$ 获得,或者如果没有这样的 $$$t$$$,则打印 $$$-1$$$。
示例
输入复制
5 4 ()() 6 ((())( 10 ))(())())( 8 )))))))) 1 (
输出复制
()() -1 -1 (())(()) -1
注意
在第一个测试用例中,字符串 "()()" 已经是一个常规的括号序列。无需更改。
在第二个和第三个测试用例中,不可能从 $$$s$$$ 到达常规括号字符串。
在第四个测试用例中,我们可以执行以下操作:
"))))))))" $$$\xrightarrow{i = 1}$$$ "(())))))"
"(())))))" $$$\xrightarrow{i = 5}$$$ "(())(())".