#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 { int l=0; int m=1; static ulamek norm(ulamek x) { /*int 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(int l_, int m_) : l(l_), m(m_) { int 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) { int 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; int idx, unique_id; friend bool operator<(Seg x, Seg y) { if(x.b!=y.b) return x.b < y.b; 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); int n, l; cin >> n >> l; int cnt = 0; vector<Seg> segments; vector<vector<Seg>> my_Seg(n); for(int i=0; i<n; ++i) { vector<ulamek> vals(l, {0,1}); int suma = 0; for(int 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); int 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, cnt}); my_Seg[i].push_back({L, R, i, cnt}); cnt++; L = R; left = ulamek(suma, n); } } sort(segments.begin(), segments.end(), comp_a); int del = 0; vector<Seg> best; for(auto s : segments) best.push_back(s); sort(best.begin(), best.end()); vector<bool> delt(cnt, 0); vector<int> perm; vector<ulamek> poz; int kursor = 0; while(kursor < best.size()) { Seg sss = best[kursor]; perm.push_back(sss.idx + 1); for(auto x : my_Seg[sss.idx]) { delt[x.unique_id] = 1; } while(del < segments.size() && segments[del].a < sss.b) { delt[segments[del].unique_id] = 1; ++del; } poz.push_back(sss.b); while(kursor < best.size() && delt[best[kursor].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; }