CF1575A.Another Sorting Problem

Andi and Budi were given an assignment to tidy up their bookshelf of $n$ books. Each book is represented by the book title — a string $s_i$ numbered from $1$ to $n$, each with length $m$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string $a$ occurs before a string $b$ in asc-desc-ending order if and only if in the first position where $a$ and $b$ differ, the following holds:

• if it is an odd position, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$;
• if it is an even position, the string $a$ has a letter that appears later in the alphabet than the corresponding letter in $b$.

安迪和布迪接到一项任务，整理他们共 $n$ 本书的书架。每本书用其书名——一个字符串 $s_i$ 表示，编号从 $1$ 到 $n$，每个字符串长度均为 $m$。安迪希望将这些书按字典序升序排列，而布迪则希望按字典序降序排列。

为解决争执，他们决定融合彼此的想法，采用“升-降交替排序”（asc-desc-endingly）：即在比较字符串时，奇数位置上的字符按升序比较，偶数位置上的字符按降序比较。

字符串 $a$ 在升-降交替序中排在字符串 $b$ 之前，当且仅当在 $a$ 和 $b$ 首次出现差异的位置 $k$ 处，满足以下条件之一：

• 若 $k$ 是奇数位置，则 $a$ 在该位置上的字母在字母表中早于 $b$ 对应位置上的字母；
• 若 $k$ 是偶数位置，则 $a$ 在该位置上的字母在字母表中晚于 $b$ 对应位置上的字母。

The first line contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 10^6$).

The $i$-th of the next $n$ lines contains a string $s_i$ consisting of $m$ uppercase Latin letters — the book title. The strings are pairwise distinct.

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

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

Output $n$ integers — the indices of the strings after they are sorted asc-desc-endingly.

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

The following illustrates the first example.

以下展示了第一个示例。