#include using namespace std; typedef long long signed int LL; typedef long long unsigned int LU; #define incID(i, l, r) for(int i = (l) ; i < (r); i++) #define incII(i, l, r) for(int i = (l) ; i <= (r); i++) #define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--) #define decII(i, l, r) for(int i = (r) ; i >= (l); i--) #define inc(i, n) incID(i, 0, n) #define inc1(i, n) incII(i, 1, n) #define dec(i, n) decID(i, 0, n) #define dec1(i, n) decII(i, 1, n) #define inII(v, l, r) ((l) <= (v) && (v) <= (r)) #define inID(v, l, r) ((l) <= (v) && (v) < (r)) #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second #define UB upper_bound #define LB lower_bound #define PQ priority_queue #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define FOR(it, v) for(auto it = v.begin(); it != v.end(); ++it) #define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it) template bool setmin(T & a, T b) { if(b < a) { a = b; return true; } else { return false; } } template bool setmax(T & a, T b) { if(b > a) { a = b; return true; } else { return false; } } template bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } } template bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } } template T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); } template T lcm(T a, T b) { return a / gcd(a, b) * b; } // ---- ---- const int Q = 150000; LL n, q, x[Q], l[Q], r[Q]; vector v; map id; int cn[600]; // full の色の数 pair f[600]; pair p[600][500]; LL ps[600][6]; // part だけの総和 LL ans[6], MOD = 1e18 + 9; LL val(int i) { return (i < v.size() ? v[i] : v.back()); } void fall(int i) { if(cn[i] == 0) { return; } inc(j, 500) { p[i][j] = MP(f[i].FI, f[i].SE + (cn[i] == 1 && p[i][j].FI == f[i].FI ? p[i][j].SE : 0)); } inc1(j, 5) { ps[i][j] = 0; } inc(j, 500) { ps[i][p[i][j].FI] += p[i][j].SE * (val(i * 500 + j + 1) - val(i * 500 + j)); } cn[i] = 0; f[i] = MP(0, 0); } void count() { inc(i, 600) { fall(i); } inc(i, 600) { inc1(j, 5) { (ans[j] += ps[i][j]) %= MOD; } } } void solve(int x, int l, int r) { LL sum[6]; inc1(i, 5) { sum[i] = 0; } inc(i, 600) { int il = i * 500; int ir = (i + 1) * 500; if(ir <= l || r <= il) { continue; } if(l <= il && ir <= r) { // full if(x == 0) { sum[f[i].FI] += f[i].SE * (val(ir) - val(il)); if(cn[i] == 1) { sum[f[i].FI] += ps[i][f[i].FI]; } if(cn[i] == 0) { inc1(j, 5) { sum[j] += ps[i][j]; } } } else { if(f[i].FI == x) { f[i].SE++; } else { f[i] = MP(x, 1); cn[i]++; } } } else { // part if(x != 0) { fall(i); } int b = max(l, il); int e = min(r, ir); incID(jj, b, e) { int j = jj % 500; LL w = val(jj + 1) - val(jj); if(x == 0) { sum[f[i].FI] += f[i].SE * w; sum[p[i][j].FI] += (cn[i] == 0 || (cn[i] == 1 && p[i][j].FI == f[i].FI) ? p[i][j].SE * w : 0); } else { if(p[i][j].FI != x) { ps[i][p[i][j].FI] -= p[i][j].SE * w; p[i][j].SE = 0; } p[i][j].FI = x; p[i][j].SE++; ps[i][x] += w; } } } } if(x == 0) { vector> vp; inc1(i, 5) { vp.EB(sum[i], i); } sort(RALL(vp)); if(vp[0].FI != vp[1].FI) { (ans[vp[0].SE] += vp[0].FI) %= MOD; } } } int main() { cin >> n >> q; inc(i, q) { cin >> x[i] >> l[i] >> r[i]; r[i]++; } inc(i, q) { v.PB(l[i]); v.PB(r[i]); } sort(ALL(v)); v.erase(unique(ALL(v)), v.end()); inc(i, v.size()) { id[v[i]] = i; } inc(i, q) { solve(x[i], id[l[i]], id[r[i]]); } count(); inc1(i, 5) { cout << (i == 1 ? "" : " ") << ans[i]; } cout << endl; return 0; }