/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.04.15
 *
 * Time: O(n * 2^k * log)
 * Memory usage: O(n) = 32.5 mb
 * AC: 1.891 seconds (0.313 + 1.578 seconds)
 */

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

public class similar_sk_Sort {
  final int maxN = 50000;
  final int maxK = 6;

  final int P = (int)1e9 + 9;

  int n, k;
  String[] s = new String[maxN];
  char[] res = new char[maxN];
  int[] ri = new int[maxN];
  long[] deg = new long[maxK], hash = new long[maxN];
  Box[] p;

  public class Box implements Comparable<Box> {
    public int i;
    public Box( int j ) { i = j; }
    public int compareTo( Box b ) {
      if (hash[i] < hash[b.i])
        return -1;
      if (hash[i] > hash[b.i])
        return 1;
      return 0;
    }
  }

  public void go( int i, int bn ) {
    if (i == k) {
      Arrays.sort(p);
      for (int t = 0; t < n - 1; t++) {
        if (hash[p[t].i] == hash[p[t + 1].i]) {
          int j = p[t].i, l = p[t + 1].i;
          if (res[l] > bn) {
            res[l] = (char)bn; ri[l] = j;
          }
          if (res[j] > bn) {
            res[j] = (char)bn; ri[j] = l;
          }
        }
      }
      return;
    }
    go(i + 1, bn + 1);
    for (int j = 0; j < n; j++)
      hash[j] += deg[i] * s[j].charAt(i);
    go(i + 1, bn);
    for (int j = 0; j < n; j++)
      hash[j] -= deg[i] * s[j].charAt(i);
  }

  public static void main( String[] args ) throws Exception {
    new similar_sk_Sort().run();
  }

  public void run() throws Exception {
    long start = System.currentTimeMillis();
    BufferedReader buf = new BufferedReader(new FileReader("similar.in"));
    PrintWriter out = new PrintWriter(new File("similar.out"));

    StringTokenizer st = new StringTokenizer(buf.readLine());
    n = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    for (int i = 0; i < n; i++) {
      s[i] = buf.readLine();
      res[i] = (char)(k + 1);
    }
    deg[0] = 1;
    for (int i = 0; i < k - 1; i++)
      deg[i + 1] = deg[i] * P;
    p = new Box[n];
    for (int i = 0; i < n; i++)
      p[i] = new Box(i);
    go(0, 0);
    for (int i = 0; i < n; i++)
      out.println((int)res[i] + " " + (ri[i] + 1));
    out.close();
    System.out.println("time = " + 1e-3 * (System.currentTimeMillis() - start));
  }
}