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

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

public class similar_sk_HashMap {
  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];

  HashMap<Long, Integer> h = new HashMap<Long, Integer>(maxN);

  public void go( int i, int bn ) {
    if (i == k) {
      h.clear();
      for (int j = 0; j < n; j++) {
        Integer last = h.put(hash[j], j);
        if (last != null) {
          int l = last;
          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_HashMap().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;
    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));
  }
}