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