#P1575A. Another Sorting Problem

    ID: 387 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structuressortingsstrings*1100

Another Sorting Problem

No submission language available for this problem.

Description

Andi and Budi were given an assignment to tidy up their bookshelf of nn books. Each book is represented by the book title — a string sis_i numbered from 11 to nn, each with length mm. 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 aa occurs before a string bb in asc-desc-ending order if and only if in the first position where aa and bb differ, the following holds:

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

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

The ii-th of the next nn lines contains a string sis_i consisting of mm uppercase Latin letters — the book title. The strings are pairwise distinct.

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

Input

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

The ii-th of the next nn lines contains a string sis_i consisting of mm uppercase Latin letters — the book title. The strings are pairwise distinct.

Output

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

Samples

Sample Input 1

5 2
AA
AB
BB
BA
AZ

Sample Output 1

5 2 1 3 4

Note

The following illustrates the first example.