题目描述

Aki有一个只包含 "(" 和 ")" 括号串 s。
原本的 s 是合法的括号序列，但粗心的Aki不小心将其打乱了，导致有一些位置的括号变成相反的括号，比如有些位置原本是 "("，打乱后变成了 ")"；有些位置本身是 ")"，打乱后变成了 "("。
现在Aki只记得打乱后的括号结果 t，他想将 t 复原为 s，但有可能复原结果不唯一，请你帮帮他吧。(如果不存在合法的复原结果，则说明Aki记错了 t 的样子，输出 -1 即可。)

合法括号串的定义： 例如"(())" 和 "()()" 是合法的括号序列。

更严格地，一个括号序列被称为合法的括号序列，当且仅当：

1. 空串是合法的括号序列；
2. 如果 A 是合法的括号序列，那么 "(A)" 也是合法的括号序列；
3. 如果 A 和 B 都是合法的括号序列，那么 AB 也是合法的括号序列。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 T ($1 ≤ T ≤ 10^3$) 代表数据组数，每组测试数据描述如下：
在一行上输入一个长度不超过 $10^6$，仅由 "(" 和 ")" 组成的括号串 t 代表打乱后的括号序列。
除此之外，保证单个测试文件的 t 的字符数量之和不超过 $2 × 10^6$。

输出格式

对于每一组测试数据：

• 如果复原结果唯一，则输出这个唯一的复原结果，即 s 括号串。
• 如果复原结果不唯一，则输出 There are multiple solutions 。
• 如果不存在任何合法的复原结果，则输出 -1 。

3
((
)
())(()()()())))((()())()

()
-1
There are multiple solutions