CF2143E.Make Good

给定一个长度为 $n$ 的括号字符串 $s$。你可以对其执行如下任意次数（可以为零次，顺序不限）的操作：

• 选择一个下标 $1 \leq i < |s|$，若 $s_i = s_{i+1} = ($，则将 $s_i$ 和 $s_{i+1}$ 都替换为 $)$。
• 选择一个下标 $1 \leq i < |s|$，若 $s_i = s_{i+1} = )$，则将 $s_i$ 和 $s_{i+1}$ 都替换为 ($。

找出一个可以通过上述操作从 $s$ 得到的合法括号序列 $t$，如果不存在则输出 $-1$。

一个合法的括号序列是指，通过在原序列的括号之间插入“1”和“+”字符，可以得到一个正确的算术表达式。例如：括号序列 "()()" 和 "(())" 是合法的（对应表达式为 "(1)+(1)" 和 "((1+1)+1)"）；而")("、"(" 和 ")"都是不合法的。

每组测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示字符串的长度。

第二行包含一个仅由字符 "(" 和 ")" 组成的、长度为 $n$ 的字符串 $s$。

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

对于每个测试用例，输出可以通过操作得到的一个合法括号序列 $t$。如果无法得到合法括号序列，输出 $-1$。

在第一个测试用例中，字符串"()()"已经是一个合法的括号序列，无需任何操作。

在第二个和第三个测试用例中，无法通过操作将 $s$ 变为合法括号序列。

在第四个测试用例中，可以如下操作：

"))))))))" $\xrightarrow{i = 1}$ "(())))))"

"(())))))" $\xrightarrow{i = 5}$ "(())(())"。

由 ChatGPT 5 翻译