/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.04.10
 *
 * Time: O(n * 2^k)
 * Memory usage: O(n) = 2 mb
 * AC: 0.234 seconds
 */

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

#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

int _bn;

inline void relax( int i, int j )
{
  if (res[i] > _bn)
    res[i] = _bn, ri[i] = j;
}

template <const int max_size, typename HashType>
struct hashTable
{
  // max_size * 11 bytes
  char cc, used[max_size]; 
  HashType hash[max_size];
  word last[max_size];

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

  inline void add( HashType H, word x )
  {
    int p = H % 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
      relax(last[p], x), relax(x, last[p]);
  }
};

hashTable<(int)8e4 + 21, ll> h; // 880 K

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