#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2010;
int ans[N];
ll V[N][N];
ll S[N][N];
int A[N];
int B[N];
int n, m;
ll get(int i, int j){
int r = j / n;
return S[i][r] * 1ll * n + V[i][r + 1] * 1ll * (j % n) ;
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
cin >> n >> m;
vector<int> ord;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
cin >> V[i][j];
S[i][j] = V[i][j] + S[i][j - 1];
}
ord.push_back(i);
}
// 1...n * m
ll R;
int las = 0;
int nx = 0;
int chk;
int low;
int idx;
for(int i = 1; i + 1 <= n; i ++ ){
low = (int)1e9;
idx = -1;
for(auto x : ord){
R = S[x][m];
nx = las;
for(int lg = 25; lg >= 0; lg -- ){
chk = (nx + (1 << lg));
if(chk < n * m){
if(get(x, chk) - get(x, las) < R){
nx = chk;
}
}
}
nx ++ ;
if(nx < low){
low = nx;
idx = x;
}
}
A[i] = low;
B[i] = n;
ans[idx] = i;
vector<int> nn;
for(auto x : ord){
if(x != idx){
nn.push_back(x);
}
}
ord = nn;
las = low;
}
ans[ord[0]] = n;
for(int i = 1; i <= n - 1; i ++ ){
cout << A[i] << " " << B[i] << "\n";
}
for(int i = 1; i <= n; i ++ ){
cout << ans[i] << " ";
}
cout << "\n";
return 0;
}
