#GYM104768G. Hard Brackets Problem
Hard Brackets Problem
本题没有可用的提交语言。
Description
Putata is coding with his favorite IDE. The best part of this IDE is the parentheses completion function. The function works as follows: assume that $S|T$ is currently displayed on the screen, where | is the current position of the cursor and $S$ and $T$ are two (possibly empty) strings.
- Putata enters left parenthesis '(', $S(|)T$ will be displayed on the screen, where | is the new position of the cursor.
- Putata enters right parenthesis ')'. If $T=)T'$, which means that $T$ begins with a right parenthesis, then the string will not change, and the cursor will move to the right of the next character, $S)|T'$ will be displayed on the screen, otherwise $S)|T$ will be displayed on the screen.
Putata worked very hard last night and when he wakes up in the morning, he only remembers the code saved on his computer and that he only entered several parentheses. Help him find the parenthesis sequence he typed in order or tell him it is impossible to type this string by only entering parentheses.
The first line contains an integer $t$ ($1\leq t\leq 10^6$), denoting the number of test cases.
For each test case, the only line contains one string $S$ ($1\leq |S|\leq 10^6$). It is guaranteed that $S$ only consists of parentheses, '(' and ')'.
It is guaranteed that the sum of $|S|$ over all testcases does not exceed $10^6$.
For each test case, if it is possible to type the string by entering parentheses, output one string in one line, denoting the answer. Otherwise, output "impossible" in one line. If there are multiple answers, you can output any of them.
Please notice that you don't have to minimize the length of the answer. Your answer should only contain parentheses and the length of your answer should be no greater than the input string for each test case if the answer exists.
Input
The first line contains an integer $t$ ($1\leq t\leq 10^6$), denoting the number of test cases.
For each test case, the only line contains one string $S$ ($1\leq |S|\leq 10^6$). It is guaranteed that $S$ only consists of parentheses, '(' and ')'.
It is guaranteed that the sum of $|S|$ over all testcases does not exceed $10^6$.
Output
For each test case, if it is possible to type the string by entering parentheses, output one string in one line, denoting the answer. Otherwise, output "impossible" in one line. If there are multiple answers, you can output any of them.
Please notice that you don't have to minimize the length of the answer. Your answer should only contain parentheses and the length of your answer should be no greater than the input string for each test case if the answer exists.
3
((()))
(
)))()
(((
impossible
)))(