| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 3 | 3 | 3 | 100.000% |
There are $N$ strings $s_1, s_2, \dots, s_N$ which are compressed by rules below. Decompress these strings, and sort them in lexicographical order. Since the length of the decompressed string is very long, you have to answer the permutation $P = (p_1, p_2, \dots, p_N)$, which is the permutation of $(1, 2, \dots, N)$ and satisfies $s_{p_1} ≤ s_{p_2} ≤ \cdots ≤ s_{p_N}$. If two decompressed strings $s_i$, $s_j$ ($i < j$) are the same, $i$ must appear before $j$ in $P$.
We compress $m$-times repetitions of a non-empty sequence 'seq' into 'm(seq)', where $m$ is a natural number greater than or equal to two and the length of 'seq' is at least one. When 'seq' consists of just one letter 'c', we may omit parentheses and write 'mc'. Formally, a compressed string is defined by following BNF.
<String> ::= <Letter> | <Number> <Letter> | <Number> '(' <String> ')' | <String> <String>
<Letter> ::= 'A' | 'B' | … | 'Z'
<Number> ::= <Digit> | <Number> '0' | <Number> <Digit>
<Digit> ::= '1' | '2' | … | '9'
For example,
'JAGJAGJAGICPCICPCJAGJAGJAGICPCICPCXXXXXXXXXX'
can be compressed into:
'3(JAG)ICPCICPCJAGJAGJAGICPCICPCXXXXXXXXXX'
by replacing the first occurrence of 'JAGJAGJAG' with its compressed form. Similarly, by replacing the following repetitions of 'ICPC', 'JAG', and 'X', we get:
'3(JAG)2(ICPC)3(JAG)2(ICPC)10X'
Since 'X' is a single letter, parentheses are omitted in this compressed representation. Finally, we have:
'2(3(JAG)2(ICPC))10X'
by compressing the repetitions of '3(JAG)2(ICPC)'. As you may notice from this example, parentheses can be nested.
The input consists of a single test case of the following format.
$N$
$s_1$
$s_2$
$\vdots$
$s_N$
The first line consists of an integer $N$ between $1$ and $50$, inclusive. This represents the number of compressed strings.
The $i$-th of the following $N$ lines consists of a compressed string $s_i$. The length of $s_i$ is at least $1$, and less than or equal to $2\,000$. For each $s_i$, the length of the decompressed string is less than or equal to $10^{10}$.
Output $N$ lines. If the decompressed $s_x$ is the $i$-th lexicographically smallest string, print $x$ in the $i$-th line.
4 3(AB)C A3(BA) ABABABC 2(5A)
4 2 1 3
5 2(2(2(2A))) 4(4A) 16A 8A8A 8AA
5 1 2 3 4