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. 

Input

The first line contains two integers n and m (1 ≤ n ⋅ m ≤ 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

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

Example

Input


5 2
AA
AB
BB
BA
AZ


Output


5 2 1 3 4

Note

The following illustrates the first example.

<image>
import com.sun.source.tree.Tree;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solution solver = new Solution();
        boolean multipleTC = false;
        int testCount = multipleTC ? Integer.parseInt(in.next()) : 1;
        for (int i = 1; i <= testCount; i++) solver.solve(in, out, i);
        out.close();
    }

    static class Solution {
        PrintWriter out;
        InputReader in;


        public void solve(InputReader in, PrintWriter out, int test) {
            this.out = out;
            this.in = in;
            int n = ni();
            m = ni();
            Pair[] arr = new Pair[n];
            for(int i = 0; i < n; i++)
                arr[i] = new Pair(n(), i);
            Arrays.sort(arr, com);
            for(int i = 0; i < n; i++) {
                out.print(arr[i].ind + 1 + " ");
            }
            pn("");
        }

        private static int m;
        static final Comparator<Pair> com = new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                for(int i = 0; i < m; i++) {
                    if(o1.st.charAt(i) != o2.st.charAt(i)) {
                        if(i % 2 == 0)
                            return Character.compare(o1.st.charAt(i), o2.st.charAt(i));
                        else
                            return Character.compare(o2.st.charAt(i), o1.st.charAt(i));
                    }
                }
                return Integer.compare(o1.ind, o2.ind);
            }
        };

        String n() {
            return in.next();
        }

        int ni() {
            return in.nextInt();
        }

        long nl() {
            return in.nextLong();
        }

        void pn(long zx) {
            out.println(zx);
        }

        void pn(String sz) {
            out.println(sz);
        }

        void pn(double dx) {
            out.println(dx);
        }

        class Pair {
            String st;
            int ind;
            Pair(String st, int ind) {
                this.st = st;
                this.ind = ind;
            }
        }
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}
