#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
using ll = long long;
using i128 = __int128;
#define debug(x) #x << " = " << x << '\n'
#define int ll
struct Fractie {
int x, y;
Fractie() {}
Fractie(int _x, int _y) : x(_x), y(_y) {}
Fractie(int _x) : x(_x), y(1) {}
void normMe() {
int d = std::__gcd(x, y);
x /= d;
y /= d;
}
Fractie friend norm(const Fractie &other) {
Fractie f = other;
f.normMe();
return f;
};
Fractie operator * (const Fractie &other) const {
return norm(Fractie(x * other.x, y * other.y));
};
Fractie operator + (const Fractie &other) const {
return norm(Fractie(x * other.y + other.x * y, y * other.y));
};
Fractie operator - (const Fractie &other) const {
return norm(*this + Fractie(-other.x, other.y));
}
Fractie operator / (const Fractie &other) const {
return norm(*this * Fractie(other.y, other.x));
}
bool operator < (const Fractie &other) const {
return x * other.y < y * other.x;
};
bool operator == (const Fractie &other) const {
return x * other.y == y * other.x;
};
bool operator > (const Fractie &other) const {
return x * other.y > y * other.x;
};
bool operator <= (const Fractie &other) const {
return x * other.y <= y * other.x;
};
bool operator >= (const Fractie &other) const {
return x * other.y >= y * other.x;
};
};
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll _n, _L;
std::cin >> _n >> _L;
int n, L;
n = _n;
L = _L;
std::vector<std::vector<int>> a(n, std::vector<int>(L));
for (int i = 0; i < n; i++) {
for (int j = 0; j < L; j++) {
ll x;
std::cin >> x;
a[i][j] = x;
}
}
std::vector<std::vector<Fractie>> splits(n);
for (int i = 0; i < n; i++) {
Fractie need(0, 1);
for (int j = 0; j < L; j++) {
need = need + a[i][j];
}
need = need / n;
need.normMe();
int complete = 0;
Fractie partial = 0;
for (int _ = 0; _ < n; _++) {
if (partial == 1) {
partial = 0;
complete++;
}
Fractie me = (Fractie(1, 1) - partial) * a[i][complete];
me.normMe();
if (me >= need) {
// x * a[i][j] = need
Fractie x = need / a[i][complete];
partial = partial + x;
splits[i].push_back(partial + complete);
continue;
}
partial = 0;
while (me < need) {
me = me + a[i][++complete];
}
me = me - a[i][complete];
// me + x * a[i][complete] == need
Fractie x = (need - me) / a[i][complete];
partial = x;
splits[i].push_back(partial + complete);
}
}
for (int i = 0; i < n; i++) {
for (auto &f : splits[i]) {
f.normMe();
}
}
std::vector<Fractie> split;
std::vector<int> order;
std::vector<int> remaining(n);
for (int i = 0; i < n; i++) {
remaining[i] = i;
}
split.push_back(Fractie(0, 1));
while (!remaining.empty()) {
Fractie mini = Fractie(1e9, 1);
int where = -1;
for (int i : remaining) {
if (splits[i][0] < mini) {
mini = splits[i][0];
where = i;
}
}
assert(where != -1);
split.push_back(splits[where][0]);
order.push_back(where);
remaining.erase(std::find(remaining.begin(), remaining.end(), where));
for (int i : remaining) {
splits[i].erase(splits[i].begin());
}
}
split.erase(split.begin());
split.pop_back();
for (auto &f : split) {
f.normMe();
assert(1 <= f.y && f.y <= 1e9);
std::cout << (ll) f.x << ' ' << (ll) f.y << '\n';
}
for (int x : order) {
std::cout << (ll) x + 1 << ' ';
}
return 0;
}
