/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.04.15
 *
 * Time: O(n * 2^k * log)
 * Memory usage: O(n) = 4 mb
 * TL: 1.813 seconds
 */

#include <ctime>
#include <cstdio>
#include <cassert>
#include <map>

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int maxN = 50000;
const int maxK = 6;

typedef unsigned short word;
typedef unsigned long long ll;

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

int n, k;
char s[maxN][maxK + 1]; // 350 K
char res[maxN]; // 50 K
word ri[maxN]; // 100 K
ll deg[maxK], hash[maxN]; // 400 K

std::map <ll, int> h;

void go( int i, int bn )
{
  if (i == k)
  {
    h.clear();
    forn(j, n)
    {
      int &last = h[hash[j]];
      if (last)
      {
        int l = last - 1;
        if (res[l] > bn) res[l] = bn, ri[l] = j;
        if (res[j] > bn) res[j] = bn, ri[j] = l;
      }
      last = j + 1;
    }
    return;
  }
  go(i + 1, bn + 1);
  forn(j, n)
    hash[j] += deg[i] * s[j][i];
  go(i + 1, bn);
  forn(j, n)
    hash[j] -= deg[i] * s[j][i];
}

int main()
{
  #define NAME "similar"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  assert(scanf("%d%d " , &n, &k) == 2 && n <= maxN && k <= maxK);
  forn(i, n)
    assert(gets(s[i])), res[i] = k + 1;
  deg[0] = 1;
  forn(i, k - 1)
    deg[i + 1] = deg[i] * P;
  go(0, 0);
  forn(i, n)
    printf("%d %d\n", res[i], ri[i] + 1);
  fprintf(stderr, "time = %.2f\n", 1.0 * clock() / CLOCKS_PER_SEC);
  return 0;
}