/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.04.12
 *
 * Time: O(n * 2^k)
 * Memory usage: O(n) = 2 mb
 * AC: 0.766 seconds (0.3 for reading + 0.466 seconds)
 */

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

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

  char _bn;

  public class hashTable {
    final int max_size = (int)8e4 + 21;
    char cc, used[] = new char[max_size]; 
    long hash[] = new long[max_size];
    int last[] = new int[max_size];

    public hashTable() { cc = 1; }
    public void clear() { cc++; }

    public void add( long H, int x ) {
      int p = (int)(H % max_size);
      if (p < 0)
        p += max_size;
      while (used[p] == cc && hash[p] != H)
        if (++p == max_size)
          p = 0;

      if (used[p] != cc) {
        used[p] = cc; hash[p] = H; last[p] = x;
      } else {
        if (res[last[p]] > _bn) {
          res[last[p]] = _bn; ri[last[p]] = x;
        }
        if (res[x] > _bn) {
          res[x] = _bn; ri[x] = last[p];
        }
      }
    }
  };

  hashTable h = new hashTable();

  public void go( int i, int bn ) {
    if (i == k) {
      _bn = (char)bn;
      h.clear();
      for (int j = 0; j < n; j++)
        h.add(hash[j], j);
      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().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));
  }
}