← 返回题目列表

Codeforces · 1211/F

F. 科特林科特林科特林科特林……

中文机器翻译题面 查看原题

Polycarp 非常喜欢写“kotlin”这个词。这个词他连续写了好几遍,中间没有空格。例如,他可以写“kotlinkotlinkotlinkotlin”这样的字符串。

Polycarp 将书写的字符串切成 $$$n$$$ 块并将它们混合。结果,他有 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_n$$$ 并且他可以按正确的顺序排列它们,连接(连接)所有这些字符串并得到一个像“kotlinkotlin...kotlin”这样的字符串。

帮助 Polycarp 找到字符串 $$$s_1, s_2, \dots, s_n$$$ 的正确顺序,这样如果他按照这个顺序写下字符串,他就会得到单词“kotlin”或者这个单词的序列。

请注意,您必须使用所有给定的字符串,并且每个字符串只能使用一次。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — Polycarp 字符串的数量。输入的下一行包含 $$$n$$$ Polycarp 的字符串。

它们的长度总和不超过$$$3\cdot10^5$$$。可以保证字符串的排列顺序正确,如果将它们连接成一个字符串,您将得到单词“kotlin”的一些非空序列。

输出

打印 $$$n$$$ 不同的整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是字符串的索引,该字符串应该是所需串联中的第 $$$i$$$ 个字符串。换句话说,连接 $$$s_{p_1}+s_{p_2}+\dots+s_{p_n}$$$ 的结果必须采用“kotlinkotlin...kotlin”的形式。如果有很多解决方案,请打印其中任何一个。

示例

输入 #1

2
lin
kot

输出 #1

2 1

输入 #2

4
linkotlinkotlinkotl
kotlin
in
kot

输出 #2

2 4 1 3

输入 #3

8
i
n
tlin
o
ko
t
k
l

输出 #3

7 4 3 5 6 8 1 2