/**
* 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;
}