#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; #define MAX 200002 #define __int128 long long int __int128 n; vector<__int128> v; __int128 MOD = 1000000000000000009LL; struct st{ int ty; __int128 l; __int128 r; st(){ long long int ll, rr; scanf("%d%lld%lld", &ty, &ll, &rr); l = ll; r = rr; } }; vector vv; struct s{ __int128 area = 0; int col = -1; __int128 l = -1; __int128 r = -1; __int128 ar[5]; __int128 add = 0; bool flag = false; int ge = -1; s(){ for (int i = 0; i < 5; i++){ ar[i] = 0; } } }; #define MAXX 300012 s seg[MAXX * 4]; void cflag(int b, int x, __int128 k){ if (seg[b].col != x){ seg[b].col = x; seg[b].add = 0; } seg[b].add += k; if (seg[b].ge != x){ seg[b].flag = true; } } void init(int b, int l, int r){ seg[b].l = l; seg[b].r = r; seg[b].area = v[r] - v[l]; if (l + 1 == r){ return; } init(b * 2 + 1, l, (l + r) >> 1); init(b * 2 + 2, (l + r) >> 1, r); } void chang(int b, int x){ seg[b].ge = x; for (int i = 0; i < 5; i++){ if (i == x){ seg[b].ar[i] += seg[b].area*seg[b].add; } else{ seg[b].ar[i] = 0; } } if (seg[b].l + 1 != seg[b].r){ cflag(b * 2 + 1, x, seg[b].add); cflag(b * 2 + 2, x, seg[b].add); } seg[b].col = -1; seg[b].add = 0; } void update(int b){ if (seg[b].col == -1){ return; } if (seg[b].flag){ for (int i = 0; i < 5; i++){ seg[b].ar[i] = 0; } } seg[b].flag = false; chang(b, seg[b].col); seg[b].col = -1; return; } inline void add(int b, int l, int r, int ll, int rr, int x){ update(b); if (rr <= l || r <= ll){ return; } if (ll <= l&&r <= rr){ cflag(b, x,1LL); update(b); return; } add(b * 2 + 1, l, (l + r) >> 1, ll, rr, x); add(b * 2 + 2, (l + r) >> 1, r, ll, rr, x); seg[b].ge = -1; for (int i = 0; i < 5; i++){ seg[b].ar[i] = seg[b * 2 + 1].ar[i] + seg[b * 2 + 2].ar[i]; } } __int128 sum[5]; inline void q(int b, int l, int r, int ll, int rr){ update(b); if (rr <= l || r <= ll){ return; } if (ll <= l&&r <= rr){ for (int i = 0; i < 5; i++){ sum[i] += seg[b].ar[i]; } return; } q(b * 2 + 1, l, (l + r) >> 1, ll, rr); q(b * 2 + 2, (l + r) >> 1, r, ll, rr); } __int128 b[5]; void output(){ for (int i = 0; i < 5; i++){ sum[i] = 0; } q(0, 0, v.size() - 1, 0, v.size() - 1); for (int i = 0; i < 5; i++){ if (i){ printf(" "); } __int128 ans = sum[i] + b[i]; ans %= MOD; unsigned long long int outt = ans; printf("%lld", outt); } puts(""); } int main(){ scanf("%lld", &n); int qq; scanf("%d", &qq); for (int i = 0; i < qq; i++){ vv.push_back(st()); v.push_back(vv.back().l); v.push_back(vv.back().r + 1LL); } v.push_back(n); v.push_back(0); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); init(0, 0, v.size() - 1); for (int i = 0; i < qq; i++){ int ind = lower_bound(v.begin(), v.end(), vv[i].l) - v.begin(); int ind2 = lower_bound(v.begin(), v.end(), vv[i].r + 1LL) - v.begin(); if (vv[i].ty == 0){ for (int i = 0; i < 5; i++){ sum[i] = 0; } q(0, 0, v.size() - 1, ind, ind2); int ind = 0; __int128 val = -1LL; for (int i = 0; i < 5; i++){ if (val < sum[i]){ val = sum[i]; ind = i; } } int countt = 0; for (int i = 0; i < 5; i++){ if (val == sum[i]){ countt++; } } if (countt == 1){ b[ind] += val; } if (countt == 0){ return 1; } } else{ add(0, 0, v.size() - 1, ind, ind2, vv[i].ty - 1); } } output(); return 0; }