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>
//package codeforces;

import java.io.*;
import java.util.*;

public class ProblemB {
    private final static FastScanner scanner = new FastScanner();
    private final static long M = 1000000007L;

    public static void main(String[] args) throws IOException {
//        int n = scanner.nextInt();
//        for (int i = 0; i < n; i++) {
//            solve();
//        }
        solve();
    }

    public static void solve() {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.next();
        }
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i + 1);
        }
        Arrays.sort(arr, (o1, o2) -> {
            for (int i = 0; i < m; i++) {
                if (o1.charAt(i) == o2.charAt(i)) continue;
                if ((i + 1) % 2 == 0) {
                    return o2.charAt(i) - o1.charAt(i);
                } else {
                    return o1.charAt(i) - o2.charAt(i);
                }
            }
            return 0;
        });
        for (String s : arr) {
            System.out.print(map.get(s) + " ");
        }
        System.out.println();
    }

    public static long getManhattanDistance(long x1, long y1, long x2, long y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public static long lcm(long number1, long number2) {
        if (number1 == 0 || number2 == 0) {
            return 0;
        }
        long absNumber1 = Math.abs(number1);
        long absNumber2 = Math.abs(number2);
        long absHigherNumber = Math.max(absNumber1, absNumber2);
        long absLowerNumber = Math.min(absNumber1, absNumber2);
        long lcm = absHigherNumber;
        while (lcm % absLowerNumber != 0) {
            lcm += absHigherNumber;
        }
        return lcm;
    }

    static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    static void swap(long[] arr, int l, int r) {
        long temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    private static int getTickSize(char[][] mat, int i, int j) {
        if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || mat[i][j] == '.') return 0;
        mat[i][j] = '.';
        return Math.min(getTickSize(mat, i - 1, j - 1), getTickSize(mat, i - 1, j + 1));
    }

    private static Boolean isSquare(long x) {
        long y = (long) Math.sqrt(x);
        return y * y == x;
    }

    private static int getMax(int[] arr) {
        int[] copy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(copy);
        return copy[arr.length - 1];
    }

    private static double customLog(double logNumber, double base) {
        return Math.log(logNumber) / Math.log(base);
    }


    static int checkSim(String n1, String n2, int i, int j) {
        if (i >= n1.length() || j >= n2.length()) return 0;
        if (n1.charAt(i) == n2.charAt(j)) return 1 + checkSim(n1, n2, i + 1, j + 1);
        return checkSim(n1, n2, i + 1, j);
    }

    static int computeXOR(int n) {
        if (n % 4 == 0)
            return n;
        if (n % 4 == 1)
            return 1;
        if (n % 4 == 2)
            return n + 1;
        return 0;
    }

    static boolean isPowerOfTwo(long n) {
        if (n == 0)
            return false;

        double v = Math.log(n) / Math.log(2);
        return (long) (Math.ceil(v)) == (long) (Math.floor(v));
    }

    static boolean isPrime(int n) {
        if (n <= 1)
            return false;

        else if (n == 2)
            return true;

        else if (n % 2 == 0)
            return false;

        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    static boolean checkSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) return false;
        }
        return true;
    }

    static void print(int from, int to) {
        if (from <= to) {
            for (int i = from; i <= to; i++) {
                System.out.print(i + " ");
            }
        } else {
            System.out.print(from + " ");
            for (int i = 1; i <= to; i++) {
                System.out.print(i + " ");
            }
        }
    }

    static long moduloMultiplication(long a, long b, long mod) {
        long res = 0;
        a %= mod;
        while (b > 0) {
            if ((b & 1) > 0) {
                res = (res + a) % mod;
            }
            a = (2 * a) % mod;
            b >>= 1;
        }
        return res;
    }

    static long moduloPower(long x, long y, long p) {
        long res = 1L;
        x = x % p;
        while (y > 0) {
            if ((y & 1) > 0)
                res = (res * x) % p;

            y = y >> 1;
            x = (x * x) % p;
        }
        return res % p;
    }

    static int lowerBound(long a[], long x) { // x is the target value or key
        int l = -1, r = a.length;
        while (l + 1 < r) {
            int m = (l + r) >>> 1;
            if (a[m] >= x) r = m;
            else l = m;
        }
        return r;
    }

    static int upperBound(long a[], long x) {// x is the key or target value
        int l = -1, r = a.length;
        while (l + 1 < r) {
            int m = (l + r) >>> 1L;
            if (a[m] <= x) l = m;
            else r = m;
        }
        return l + 1;
    }

    static long upperBound(long[] arr, int start, int end, long k) {
        int N = end;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (k >= arr[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (start < N && arr[start] <= k) {
            start++;
        }
        return start;
    }

    static long lowerBound(long[] arr, int start, int end, long k) {
        int N = end;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (k <= arr[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        if (start < N && arr[start] < k) {
            start++;
        }
        return start;
    }

    static int getDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    static int sumOfNNaturalNumbers(int n) {
        return (n * (n + 1)) / 2;
    }

    static long sumOfNNaturalNumbers(long n) {
        return (n * (n + 1)) / 2;
    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }


    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

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

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

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