#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct ulamek {
ll l=0;
ll m=1;
static ulamek norm(ulamek x) {
ll g = gcd(x.l, x.m);
x.l /= g;
x.m /=g;
if (x.m < 0) { x.l = -x.l; x.m = -x.m; }
return x;
}
ulamek(ll l_, ll m_) : l(l_), m(m_) {
ll g = gcd(l, m);
l /= g; m /= g;
}
friend ulamek operator*(ulamek a, ulamek b) {
a.l *= b.l;
a.m *= b.m;
return norm(a);
}
friend ulamek operator+(ulamek a, ulamek b) {
ll common = a.m / gcd(a.m, b.m) * b.m;
a.l = a.l * (common / a.m);
b.l = b.l * (common / b.m);
return {a.l + b.l, common};
}
friend ulamek operator-(ulamek a, ulamek b) {
b.l *= -1;
return a + b;
}
friend ulamek operator/(ulamek a, ulamek b) {
assert(b.l != 0);
swap(b.l, b.m);
return a * b;
}
friend bool operator<(ulamek a, ulamek b) {
return a.l * b.m < a.m * b.l;
}
friend bool operator==(ulamek a, ulamek b) {
return a.l * b.m == a.m * b.l;
}
friend bool operator!=(ulamek a, ulamek b) {
return !(a == b);
}
};
struct Seg{
ulamek b;
ll unique_id;
friend bool operator<(Seg x, Seg y) {
if(x.b!=y.b) return x.b < y.b;
return x.unique_id < y.unique_id;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, l;
cin >> n >> l;
ll cnt = 0;
vector<Seg> segments;
vector<pair<Seg,int>> best;
vector<vector<int>> my_Seg(n);
for(int i=0; i<n; ++i) {
vector<ulamek> vals(l, {0,1});
ll suma = 0;
for(ll i=0; i<l; ++i) {
cin >> vals[i].l;
suma += vals[i].l;
}
vector<ulamek> orgval = vals;
ulamek left(suma, n);
ulamek L(0,1), R(0,1);
ll nxt = 0;
while(nxt < l) {
while(ulamek(0,1) < left) {
if(left < vals[nxt]) {
vals[nxt] = vals[nxt] - left;
R = R + (left / orgval[nxt]);
left = {0,1};
} else {
left = left - vals[nxt];
R = R + (vals[nxt] / orgval[nxt]);
nxt++;
}
}
segments.push_back({L,cnt});
best.push_back({{R,cnt}, i});
my_Seg[i].push_back(cnt);
cnt++;
L = R;
left = ulamek(suma, n);
}
}
ll del = 0;
sort(segments.begin(), segments.end());
sort(best.begin(), best.end());
vector<bool> delt(cnt, 0);
vector<ll> perm;
vector<ulamek> poz;
int kursor = 0;
while(kursor < best.size()) {
auto[sss,idx] = best[kursor];
perm.push_back(idx + 1);
for(auto x : my_Seg[idx]) {
delt[x] = 1;
}
while(del < segments.size() && segments[del].b < sss.b) {
delt[segments[del].unique_id] = 1;
++del;
}
poz.push_back(sss.b);
while(kursor < best.size() && delt[best[kursor].first.unique_id]) kursor++;
}
poz.pop_back();
for(auto x : poz) {
cout << x.l << " " << x.m << "\n";
}
for(auto x : perm) cout << x << " "; cout << "\n";
return 0;
}
