#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 norm({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) { a = norm(a); b = norm(b); return (a.l==b.l && a.m==b.m); } 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; }