#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <ctime>
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, std::vector<Fractie>(n));
for (int i = 0; i < n; i++) {
ll total = 0;
for (int j = 0; j < L; j++) {
total += a[i][j];
}
ll sum = 0;
for (int j = 0, p = 0; j < n; j++) {
while ((sum + a[i][p]) * n <= total * (j + 1)) {
sum += a[i][p++];
}
// ramane total - sum * n de pus
// a[i][j] * x * n = total * (j + 1) - sum * n
// x = (total * (j + 1) - sum * n) / (n * a[i][j])
Fractie extra(total * (j + 1) - sum * n, n * a[i][p]);
extra.normMe();
splits[i][j] = Fractie(p) + extra;
}
}
if (std::clock() > CLOCKS_PER_SEC) {
std::cout << -1;
return 0;
}
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));
for (int i = 0; i < n; i++) {
std::reverse(splits[i].begin(), splits[i].end());
}
while (!remaining.empty()) {
Fractie mini = Fractie(1e9, 1);
int where = -1;
for (int i : remaining) {
if (splits[i].back() < mini) {
mini = splits[i].back();
where = i;
}
}
assert(where != -1);
split.push_back(splits[where].back());
order.push_back(where);
remaining.erase(std::find(remaining.begin(), remaining.end(), where));
for (int i : remaining) {
splits[i].pop_back();
}
}
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;
}
