你的任务是对给定的 $N$ 个以压缩形式给出的字符串 $s_1, s_2, \dots, s_N$ 进行排序。

压缩方式如下：一个非空字符序列 $seq$ 重复 $m$ 次可以压缩为 “$m(seq)$”，其中 $m \ge 2$ 是一个整数。当 $seq$ 仅由一个字母 $c$ 组成时，我们可以省略括号，写成 “$mc$”。形式上，压缩字符串由以下 BNF 文法定义：

::= | | ’(’ ’)’ |

::= ’A’ | ’B’ | ... | ’Z’

::= | ’0’ |

::= ’1’ | ’2’ | ... | ’9’

例如，ACMACMACMICPCICPCACMACMACMICPCICPCXXXXXXXXXX 可以压缩为： 3(ACM)ICPCICPCACMACMACMICPCICPCXXXXXXXXXX 通过将第一次出现的 ACMACMACM 替换为其压缩形式。类似地，通过替换后续重复的 ICPC、ACM 和 X，我们得到： 3(ACM)2(ICPC)3(ACM)2(ICPC)10X 由于 X 是单个字母，在这个压缩表示中省略了括号。最后，我们得到： 2(3(ACM)2(ICPC))10X 通过压缩 3(ACM)2(ICPC) 的重复部分。正如你从这个例子中注意到的，括号可以嵌套。

输入格式

第一行包含一个整数 $N$，表示压缩字符串的数量 ($1 \le N \le 50$)。 接下来的 $N$ 行中，第 $i$ 行包含压缩字符串 $s_i$。给定压缩形式的长度在 1 到 2000 个字符之间（包含边界）。每个解压后的字符串由大写英文字母组成，其长度最大为 $10^{10}$。

输出格式

输出 $N$ 行。如果解压后的 $s_x$ 是第 $i$ 个字典序最小的字符串，则在第 $i$ 行输出 $x$。相等的字符串必须按照它们在输入中出现的顺序进行排序。

样例

输入 1

4
3(IC)PC
I3(CI)
ICICICPC
2(5I)

输出 1

2
1
3
4

输入 2

5
2(2(2(2X)))
4(4X)
16X
8X8X
8XX

输出 2

5
1
2
3
4