CF2143E Make Good

You are given a bracket string $ s $ of length $ n $ . You can apply the following operations arbitrary number of times (possibly, zero) and in any order: - Choose an index $ 1 \leq i < |s| $ such that $ s_i = s_{i+1} = \texttt{(} $ , and replace both $ s_i $ and $ s_{i+1} $ with $ \texttt{)} $ . - Choose an index $ 1 \leq i < |s| $ such that $ s_i = s_{i+1} = \texttt{)} $ , and replace both $ s_i $ and $ s_{i+1} $ with $ \texttt{(} $ . Find a regular bracket sequence $ ^{\text{∗}} $ $ t $ which can be obtained from $ s $ by applying the operations described above, or print $ -1 $ if there is no such $ t $ . $ ^{\text{∗}} $ A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example: the bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"); the bracket sequences ")(", "(" and ")" are not.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the string. The second line contains a single string $ s $ — a sequence of the characters ( and ) of length $ n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case output a regular bracket string $ t $ which can be obtained from $ s $ or print $ -1 $ if there is no such $ t $ .

In the first testcase, the string "()()" is already a regular bracket sequence. No changes needed. In the second and third testcases it's impossible to reach a regular bracket string from $ s $ . In the fourth testcase we can do the following: "))))))))" $ \xrightarrow{i = 1} $ "(())))))" "(())))))" $ \xrightarrow{i = 5} $ "(())(())".