← 返回题目列表

Codeforces · 1575/A

A. 另一个排序问题

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

安迪和布迪接到一项任务,去整理他们书架上的 $$$n$$$ 书。每本书都由书名表示 - 一个字符串 $$$s_i$$$,编号从 $$$1$$$ 到 $$$n$$$,每个长度为 $$$m$$$。 Andi 确实想按字典顺序升序对这本书进行排序,而 Budi 则想按字典顺序降序对这本书进行排序。

解决了他们的争执,他们决定结合他们的想法,将其按升序排序,其中奇数索引的字符将升序比较,偶数索引的字符将降序比较。

字符串 $$$a$$$ 按升序-降序结束顺序出现在字符串 $$$b$$$ 之前,当且仅当在第一个位置 $$$a$$$ 和 $$$b$$$ 不同时,以下情况成立:

- 如果是奇数位置,则字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的对应字母更早出现;
- 如果它是偶数位置,则字符串 $$$a$$$ 中的字母在字母表中出现的字母晚于 $$$b$$$ 中相应的字母。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含一个由 $$$m$$$ 大写拉丁字母组成的字符串 $$$s_i$$$ — 书名。这些字符串是成对不同的。

输出

输出 $$$n$$$ 整数 — 字符串按升序-降序排序后的索引。

示例

输入 #1

5 2
AA
AB
BB
BA
AZ

输出 #1

5 2 1 3 4

注意

下面说明第一个示例。