#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 a, b; ll idx; friend bool operator<(Seg x, Seg y) { if(x.a!=y.a) return x.a < y.a; return x.idx < y.idx; } void printout() { cout << idx << ": " << a.l << " " << a.m << " -> " << b.l << " " << b.m << "\n"; } }; bool comp_a(Seg x, Seg y) { if(x.a!=y.a) return x.a < y.a; return x.idx < y.idx; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, l; cin >> n >> l; vector<Seg> segments; vector<vector<Seg>> my_Seg(n); for(ll 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, R, i}); my_Seg[i].push_back({L, R, i}); L = R; left = ulamek(suma, n); } } sort(segments.begin(), segments.end(), comp_a); ll del = 0; set<Seg> best; for(auto s : segments) best.insert(s); vector<ll> perm; vector<ulamek> poz; while(best.size()) { Seg s = *best.begin(); perm.push_back(s.idx + 1); for(auto x : my_Seg[s.idx]) { best.erase(x); } while(del < segments.size() && segments[del].a < s.b) { best.erase(segments[del]); ++del; } poz.push_back(s.b); } poz.pop_back(); for(auto x : poz) { cout << x.l << " " << x.m << "\n"; } for(auto x : perm) cout << x << " "; cout << "\n"; return 0; }