问题$H$: 史前计划

时限: $6s$

题目大意：

考古学家发现了一块令人兴奋的属于史前文明的粘土石板，但是没有人能够破译石板的语言，除了两个似乎用于描述嵌套结构的符号：左括号和右括号。经过了几千年，这块粘土石板上的文字处于紊乱状态。你的工作是将它们排列成一个序列，以便生成的完整序列具有正确嵌套的括号结构。仅考虑左括号和右括号的所有序列中，正确嵌套的结构有且仅有以下三种：

• $()$
• $(A)$ ，其中$A$是正确嵌套的结构
• $AB$， 其中$A$和$B$是正确嵌套的结构。

输入格式

第一行一个整数 $n(1\le n\le 10^6)$。

接下来 $2$到$n+1$行中，每行一个括号序列$S$，保证$1\le |S| \le 10^7$

输出格式

有 $n$行

第 $i$行有一个数 $p_i$表示当前用 $S_{p_i}$字符连接。

如果没有正确的拼合方法，输出 $impossible$。

感谢CJK同学的整理。