Another Sorting Problem

题意翻译

给出 $n$ 个长度为 $m$ 的字符串，按照如下规则排序后，输出排序后每一个字符串在输入时的位置（从 $1$ 开始）。 规则： 从第 $m$ 位开始到第 $1$ 位排序，对于第 $i$ 位： $i$ 是奇数，按字典序升序排序； $i$ 是偶数，按字典序降序排序。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

5 2
AA
AB
BB
BA
AZ

输出样例 #1

5 2 1 3 4

说明

The following illustrates the first example.