#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
const ll mx = 2'000;
int N, L;
ll getgcd(ll a, ll b)
{
while(1)
{
if(a < b)
swap(a, b);
if(b == 0)
return a;
a = a % b;
}
}
struct frac
{
ll n;
ll d;
};
frac makegood(ll n, ll d)
{
if(d < 0)
{
n = -n;
d = -d;
}
ll g = getgcd(max(n, -n), d);
return frac{n/g, d/g};
}
bool operator < (frac A, frac B)
{
return A.n*B.d < B.n*A.d;
}
bool operator == (frac A, frac B)
{
return A.n*B.d == B.n*A.d;
}
bool operator > (frac A, frac B)
{
return B < A;
}
bool operator <= (frac A, frac B)
{
return A.n*B.d <= B.n*A.d;
}
frac operator + (frac A, frac B)
{
return makegood(A.n*B.d + B.n*A.d, A.d*B.d);
}
frac operator - (frac A, frac B)
{
return makegood(A.n*B.d - B.n*A.d, A.d*B.d);
}
frac operator / (frac A, frac B)
{
return makegood(A.n*B.d, B.n*A.d);
}
vvll V(1+mx, vll(1+mx, 0));
frac getVpref(int p, frac i)
{
if(i.n == i.d * L)
return {V[p][L], 1};
// return V[p][i.n/i.d] + (V[i.n/i.d + 1] - V[i.n/i.d]) * ((i.n % i.d) / i.d);
return frac{V[p][i.n/i.d]*i.d + (V[p][i.n/i.d + 1] - V[p][i.n/i.d]) * (i.n % i.d), i.d};
}
int main()
{
cin >> N >> L;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= L; j++)
{
cin >> V[i][j];
V[i][j] += V[i][j-1];
}
}
vi visit(1+N, 0);
vector<frac> X;
vector<int> P;
X.push_back({0, 1});
vector<frac> curr(1+N, frac{0, 1});
int xct = 0;
for(int t = 1; t < N; t++)
{
// cerr << "\n\n";
// cerr << "t = " << t << '\n';
int bestp = -1;
for(int i = 1; i <= N; i++)
{
if(visit[i]) continue;
while(getVpref(i, curr[i]) < getVpref(i, X.back()) + frac{V[i][L], N})
{
xct++;
// if(xct >= 50'000'000)
// assert(0);
if(curr[i].d == 1)
{
if(curr[i].n < L && frac{V[i][curr[i].n + 1], 1} <= getVpref(i, X.back()) + frac{V[i][L], N})
curr[i].n++;
else
{
frac thisfrac = (getVpref(i, X.back()) + frac{V[i][L], N} - getVpref(i, curr[i])) / frac{V[i][curr[i].n + 1] - V[i][curr[i].n], 1};
curr[i] = curr[i] + thisfrac;
break;
}
}
else
{
// assert(curr[i].d != 0);
curr[i] = frac{min(curr[i].n / curr[i].d + 1, ll(L)), 1};
// assert(-1000000000 <= curr[i].n);
if(getVpref(i, curr[i]) > getVpref(i, X.back()) + frac{V[i][L], N})
{
// assert(curr[i].n >= 1);
curr[i] = curr[i] - (getVpref(i, curr[i]) - (getVpref(i, X.back()) + frac{V[i][L], N})) / frac{V[i][curr[i].n] - V[i][curr[i].n - 1], 1};
}
}
}
if(bestp == -1 || curr[bestp] > curr[i])
bestp = i;
// cerr << i << " : " << curr[i].n << ' ' << curr[i].d << '\n';
}
visit[bestp] = 1;
P.push_back(bestp);
X.push_back(curr[bestp]);
}
// assert(N <= 6);
for(int i = 1; i <= N; i++)
if(!visit[i])
P.push_back(i);
for(int i = 1; i <= N-1; i++)
cout << X[i].n << ' ' << X[i].d << '\n';
for(int p : P)
cout << p << ' ';
cout << '\n';
}
