题目描述

考古学家在 Alutila Cave 的深层发现了令人兴奋的泥板。没有人能够破译泥板上的文字，除了似乎描述了嵌套结构的两个符号，这两个符号与 LISP 中的左右括号有点类似。会不会是人类在几千年前就写了程序？

综合来看，这些泥板似乎描述了一部伟大的作品——也许是一段程序，或者是一部史诗，甚至是税收记录！不足为奇的是，经过这么长的时间，这些泥板都处于无序状态。你的工作是将它们排成一个序列，使产生的序列有一个合法的括号序列。只考虑到左括号和右括号，一个合法的括号序列是：

• ()，或者
• (A)，其中 $A$ 是合法的括号序列，或者
• AB，其中 $A,B$ 都是合法的括号序列。

输入格式

输入第一行包含一个整数 $n\ (1\le n\le 10^6)$，表示泥板个数。接下来 $n$ 行，每行描述一个泥板。每行包含一个非空且由左右括号组成的字符串；与括号序列无关的符号在输入中被省略。字符串按出现在输入的顺序从 $1$ 到 $n$ 编号。输入中最多有 $10^7$ 个括号。

输出格式

输出一个 $1$ 到 $n$ 的排列，满足按这个顺序连接字符串就可以得到一个合法的括号序列。如果多个排列均可以满足条件，输出其中一个即可。如果没有满足要求的排列，输出 impossible。

2
())())()
((()

2
1

5
(
))
((
))
(

1
5
3
2
4

2
((
)

impossible