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.
5 2 AA AB BB BA AZ
5 2 1 3 4
The following illustrates the first example.
