#include #define rep(i, a) rep2 (i, 0, a) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) repr2 (i, 0, a) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; const ll mod = (ll)1e18 + 9; ll weight[1010101]; ll wsum[1010101]; ll N, Q; ll x[202020], l[202020], r[202020]; struct SegmentTree { int size; vector segt, lazyt; vector segr, lazyr; SegmentTree(int n) { size = 1; while (size < n) size *= 2; segt.resize(size * 2 - 1); lazyt.resize(size * 2 - 1); segr.resize(size * 2 - 1); lazyr.resize(size * 2 - 1); } void evallazy(int k, int l, int r) { if (lazyr[k]) { segt[k] = 0; } segt[k] += lazyt[k] * (wsum[r] - wsum[l]); if (r - l > 1) { if (lazyr[k]) { lazyt[k * 2 + 1] = 0; lazyt[k * 2 + 2] = 0; } lazyr[k * 2 + 1] = lazyr[k] || lazyr[k * 2 + 1]; lazyr[k * 2 + 2] = lazyr[k] || lazyr[k * 2 + 2]; lazyt[k * 2 + 1] += lazyt[k]; lazyt[k * 2 + 2] += lazyt[k]; } lazyt[k] = 0; lazyr[k] = false; } // q=0:set, q=1:reset void update(int a, int b, int q, int k, int l, int r) { evallazy(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { if (q == 0) { lazyt[k]++; } else { lazyt[k] = 0; lazyr[k] = true; } evallazy(k, l, r); } else { update(a, b, q, k * 2 + 1, l, (l + r) / 2); update(a, b, q, k * 2 + 2, (l + r) / 2, r); segt[k] = segt[k * 2 + 1] + segt[k * 2 + 2]; } } void update(int a, int b, int q) { update(a, b, q, 0, 0, size); } ll query(int a, int b, int k, int l, int r) { evallazy(k, l, r); if (r <= a || b <= l) return 0; if (a <= l && r <= b) return segt[k]; ll res = 0; res += query(a, b, k * 2 + 1, l, (l + r) / 2); res += query(a, b, k * 2 + 2, (l + r) / 2, r); return res; } ll query(int a, int b) { return query(a, b, 0, 0, size); } ll query() { return query(0, size); } }; template ostream &operator <<(ostream &os, const pair &p) { cout << "(" << p.first << " " << p.second << ")"; } template ostream &operator <<(ostream &os, const vector &v) { rep (i, v.size()) { if (i) cout << " "; cout << v[i]; } return os; } int main() { cin >> N >> Q; rep (i, Q) { cin >> x[i] >> l[i] >> r[i]; } if (Q == 0) { vector score(5); cout << score << endl; return 0; } vector xs; rep (i, Q) { xs.push_back(l[i]); xs.push_back(l[i] + 1); xs.push_back(r[i]); xs.push_back(r[i] + 1); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ll w = xs.size(); rep (i, xs.size() - 1) { weight[i] = xs[i + 1] - xs[i]; } rep (i, Q) { l[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin(); r[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin(); } partial_sum(weight, weight + w, wsum + 1); // main logic // cout << "main logic" << endl; vector segt(5, SegmentTree(w + 10)); vector score(5); rep (i, Q) { // cout << x[i] << " " << l[i] << " " << r[i] << endl; if (x[i] == 0) { vector> t(5); rep (j, 5) { t[j].second = j; t[j].first = segt[j].query(l[i], r[i] + 1); } sort(t.rbegin(), t.rend()); // cout << "bonus" << endl; // cout << t << endl; if (t[0].first > t[1].first) { score[t[0].second] += t[0].first; score[t[0].second] %= mod; } else { // cout << "bad" << endl; } } else { x[i]--; rep (j, 5) { segt[j].update(l[i], r[i] + 1, x[i] != j); } } // cout << score << endl; } // cout << "end query" << endl; rep (i, 5) { score[i] += segt[i].query(); score[i] %= mod; } cout << score << endl; return 0; }