1493: 小D的字符串游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:209 Solved:21

Description

小D喜欢玩字符串游戏,游戏的规则是这样的:
首先给出一个字符串,仅有'(' ')' '*'三种字符组成。其中'*'代表通配符,小D可以将任意'*'字符替换为'(' 或 ‘)'或删掉。
小D希望通过对'*'字符进行操作获得括号序列合法的字符串,同时要求字符串长度尽可能短、长度相同时候,字典序需要尽可能的小。
这就是个很棘手的问题了,小D希望你能帮他解决。
左括号的字典序小于右括号的字典序。

Input

输入包含一个整数T,表示数据组数。
接下来T行,每行输入一个字符串。

Output

输出包含T行,每行一个字符串,表示合法的字符串序列。如果无法变成合法字符串,则输出No solution!

Sample Input Copy

4
*))*)
*(*)*
********
*)*(*

Sample Output Copy

No solution!
()

()()

HINT

T<=100000
$\Sigma |S| <= 10^6$