题目描述

Andi 和 Budi 被分配了一个任务，要整理他们的书架，上面有 $n$ 本书。每本书用书名表示——一个编号为 $1$ 到 $n$ 的字符串 $s_i$，每个字符串长度为 $m$。Andi 非常希望将书按字典序升序排列，而 Budi 则想按字典序降序排列。

为了调和他们的分歧，他们决定结合两种想法，采用“升降交替排序”：奇数位置的字符按升序比较，偶数位置的字符按降序比较。

如果在第一个不同的位置，字符串 $a$ 和字符串 $b$ 满足以下条件，则在升降交替排序中，字符串 $a$ 排在字符串 $b$ 之前：

• 如果该位置是奇数，则 $a$ 在该位置的字母在字母表中比 $b$ 的对应字母靠前；
• 如果该位置是偶数，则 $a$ 在该位置的字母在字母表中比 $b$ 的对应字母靠后。

输入格式

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

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串 $s_i$，均由大写英文字母组成，且所有字符串两两不同。

输出格式

输出 $n$ 个整数，表示经过升降交替排序后字符串的下标顺序。

说明/提示

下图展示了第一个样例的排序过程。

由 ChatGPT 4.1 翻译

样例

5 2
AA
AB
BB
BA
AZ

5 2 1 3 4