安迪和布迪接到一项任务,去整理他们书架上的 $$$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
注意
下面说明第一个示例。