# include <bits/stdc++.h>
using namespace std;
using ll=long long;
int a[2010],p[2010];
bool vis[2010];
struct Frac
{
	ll x,y;
	Frac(){}
	Frac(ll x,ll y):x(x),y(y){}
	bool operator<(const Frac &t)const{return x*t.y<y*t.x;}
}b[2010][2010];
int main()
{
	int n,L;
	cin>>n>>L;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=L;j++) scanf("%d",&a[j]),a[j]+=a[j-1];
		for(int j=1,k=1;j<n;j++)
		{
			while((ll)n*a[k]<j*a[L]) k++;
			b[i][j]=Frac((ll)(k-1)*n*(a[k]-a[k-1])+(ll)j*a[L]-(ll)n*a[k-1],n*(a[k]-a[k-1]));
		}
	}
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=n;j++)
			if(!vis[j] && (!p[i] || b[j][i]<b[p[i]][i]))
				p[i]=j;
		vis[p[i]]=1;
		printf("%lld %lld\n",b[p[i]][i].x,b[p[i]][i].y);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]) p[n]=i;
	for(int i=1;i<=n;i++) printf("%d%c",p[i]," \n"[i==n]);
	return 0;
}