#include <bits/stdc++.h>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, l;
std::cin >> n >> l;
std::vector v(n, std::vector<int>(l)), pv(n, std::vector<int>(l));
for (int i = 0; i < n; ++i) {
for (auto &j : v[i]) {
std::cin >> j;
}
std::partial_sum(v[i].begin(), v[i].end(), pv[i].begin());
}
struct Fraction {
__int128_t num, den;
Fraction() : num(0), den(1) {}
Fraction(long long x) : num(x), den(1) {}
Fraction(long long num, long long den) : num(num), den(den) { reduce(); }
Fraction(__int128_t num, __int128_t den) : num(num), den(den) { reduce(); }
void reduce() {
std::function<__int128_t(__int128_t, __int128_t)> gcd;
gcd = [&](__int128_t a, __int128_t b) {
while (b != 0) {
auto temp = b;
b = a % b;
a = temp;
}
return a;
};
__int128_t d = gcd(num, den);
num /= d, den /= d;
if (num < 0 and den < 0) {
num *= -1, den *= -1;
}
}
Fraction operator+(const Fraction &other) const {
Fraction ans;
ans.num = num * other.den + other.num * den;
ans.den = den * other.den;
ans.reduce();
return ans;
}
Fraction operator-(const Fraction &other) const {
return operator+({-other.num, other.den});
}
Fraction operator*(const Fraction &other) const {
Fraction ans;
ans.num = num * other.num;
ans.den = den * other.den;
ans.reduce();
return ans;
}
bool operator<(const Fraction &other) const {
return num * other.den < other.num * den;
}
};
auto sum = [&](int i, int l, int r) {
if (l > r) {
return 0LL;
}
long long ans = pv[i][r];
if (l != 0) {
ans -= pv[i][l - 1];
}
return ans;
};
auto sum_f = [&](int i, Fraction x) {
int w = x.num / x.den;
long long full = sum(i, 0, w - 1);
x.num -= w * x.den;
return Fraction(full * x.den + x.num * v[i][w], x.den);
};
std::vector<Fraction> ans;
std::vector<int> p;
std::set<int> st;
for (int i = 0; i < n; ++i) {
st.insert(i);
}
Fraction prev = 0;
while (!st.empty()) {
std::pair<Fraction, int> min = {l + 1, -1};
for (auto &i : st) {
auto prev_sum = sum_f(i, prev);
auto idx =
*std::ranges::partition_point(std::views::iota(0, l), [&](int j) {
return Fraction(sum(i, 0, j)) - prev_sum <
Fraction(sum(i, 0, l - 1), n);
});
Fraction x =
Fraction(1LL, v[i][idx]) * (Fraction(sum(i, 0, l - 1), n) + prev_sum -
Fraction(sum(i, 0, idx - 1)));
min = std::min(min, {x + Fraction(idx), i});
}
p.push_back(min.second);
if (prev.num != 0) {
ans.push_back(prev);
}
prev = min.first;
st.erase(min.second);
}
for (auto &[a, b] : ans) {
std::cout << (long long)a << ' ' << (long long)b << '\n';
}
for (auto &i : p) {
std::cout << i + 1 << ' ';
}
std::cout << '\n';
}
