description: 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>
solution: import java.io.*;
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.StringTokenizer;
  
  public class AnotherSortingProblem  {
  
  
      static int mod = 1000000007;
      static int maxStringLen = 0;
  
      public static void main(String[] args) throws IOException {
  
          FastReader reader = new FastReader();
          FastWriter writer = new FastWriter();
          int[] nm = reader.readIntArray(2);
          int n = nm[0], m = nm[1];
          maxStringLen = m;
  
  
          ArrayList<String> original = new ArrayList<>();
          ArrayList<String> sorted = new ArrayList<>();
          for(int i = 0; i<n; i++){
              String s = reader.readString();
              original.add(s);
              sorted.add(s);
          }
  
          int[] ans = new int[n];
          HashMap<String, Integer> indices = new HashMap<>();
          sorted = sortRecursive(sorted, 0);
  
          for(int i = 0; i<original.size(); i++){
              indices.put(original.get(i), i+1);
          }
  
          for(int i = 0; i<sorted.size(); i++){
              ans[i] = indices.get(sorted.get(i));
          }
  
          writer.writeIntArrayWithSpaces(ans);
  
      }
  
  
      public static ArrayList<String> sortRecursive(ArrayList<String> bucket, int index){
  
          ArrayList<String>[] buckets = new ArrayList[26];
          for(int i = 0 ; i<26; i++){
              buckets[i] = new ArrayList<>();
          }
  
          for(int i = 0; i<bucket.size(); i++){
              buckets[bucket.get(i).charAt(index)-65].add(bucket.get(i));
          }
  
          if(index < maxStringLen-1) {
              for(int i = 0; i<buckets.length; i++){
                  if(buckets[i].size() > 0) {
                      buckets[i] = sortRecursive(buckets[i], index+1);
                  }
              }
          }
  
          ArrayList<String> ans = new ArrayList<>();
          if((index+1)%2 == 0){
              for(int i = 25; i>= 0; i--){
                  for(int j = 0; j<buckets[i].size(); j++){
                      ans.add(buckets[i].get(j));
                  }
              }
          } else {
              for(int i = 0; i<26; i++){
                  for(int j = 0; j<buckets[i].size(); j++){
                      ans.add(buckets[i].get(j));
                  }
              }
          }
  
          return ans;
      }
  
  
  
  
  
  
      public static void mergeSort(int[] a, int n) {
          if (n < 2) {
              return;
          }
          int mid = n / 2;
          int[] l = new int[mid];
          int[] r = new int[n - mid];
  
          for (int i = 0; i < mid; i++) {
              l[i] = a[i];
          }
          for (int i = mid; i < n; i++) {
              r[i - mid] = a[i];
          }
          mergeSort(l, mid);
          mergeSort(r, n - mid);
  
          merge(a, l, r, mid, n - mid);
      }
  
  
      public static void merge(int[] a, int[] l, int[] r, int left, int right) {
  
          int i = 0, j = 0, k = 0;
          while (i < left && j < right) {
              if (l[i] <= r[j]) {
                  a[k++] = l[i++];
              }
              else {
                  a[k++] = r[j++];
              }
          }
          while (i < left) {
              a[k++] = l[i++];
          }
          while (j < right) {
              a[k++] = r[j++];
          }
      }
  
  
      public static class FastReader {
  
          BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer tokenizer;
  
  
          public int readSingleInt() throws IOException {
              return Integer.parseInt(reader.readLine());
          }
  
          public int[] readIntArray(int numInts) throws IOException {
              int[] nums = new int[numInts];
              tokenizer = new StringTokenizer(reader.readLine());
              for(int i = 0; i<numInts; i++){
                  nums[i] = Integer.parseInt(tokenizer.nextToken());
              }
              return nums;
          }
  
          public String readString() throws IOException {
              return reader.readLine();
          }
  
      }
  
  
  
      public static class FastWriter {
  
          BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  
  
          public void writeSingleInteger(int i) throws IOException {
              writer.write(Integer.toString(i));
              writer.newLine();
              writer.flush();
          }
  
          public void writeSingleLong(long i) throws IOException {
              writer.write(Long.toString(i));
              writer.newLine();
              writer.flush();
          }
  
          public void writeIntArrayWithSpaces(int[] nums) throws IOException {
              for(int i = 0; i<nums.length; i++){
                  writer.write(nums[i] + " ");
              }
              writer.newLine();
              writer.flush();
          }
  
          public void writeIntArrayListWithSpaces(ArrayList<Integer> nums) throws IOException {
              for(int i = 0; i<nums.size(); i++){
                  writer.write(nums.get(i) + " ");
              }
              writer.newLine();
              writer.flush();
          }
  
          public void writeIntArrayWithoutSpaces(int[] nums) throws IOException {
              for(int i = 0; i<nums.length; i++){
                  writer.write(Integer.toString(nums[i]));
              }
              writer.newLine();
              writer.flush();
          }
  
          public void writeString(String s) throws IOException {
              writer.write(s);
              writer.newLine();
              writer.flush();
          }
  
      }
  
  
  
  }
  