#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;
struct frac
{
ll n;
ll d;
};
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 {A.n*B.d + B.n*A.d, A.d*B.d};
}
frac operator - (frac A, frac B)
{
return {A.n*B.d - B.n*A.d, A.d*B.d};
}
frac operator / (frac A, frac B)
{
return {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++)
{
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(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;
}
}
else
{
curr[i] = frac{curr[i].n / curr[i].d + 1, 1};
}
}
if(bestp == -1 || curr[bestp] > curr[i])
bestp = i;
}
visit[bestp] = 1;
P.push_back(bestp);
X.push_back(curr[bestp]);
}
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';
}
