#include using namespace std; const long long MOD = 1000000000000000009LL; vector< long long > nums; struct SegmentTree { struct node { vector< long long > Sum; int LazyColor, LazySum; node():LazyColor(-1), LazySum(0) { Sum.assign(5, 0); }; }; vector< node > seg; int sz; SegmentTree(int n) { sz = 1; while(sz < n) sz <<= 1; seg.assign(sz * 2 - 1, node()); } inline void Update(int k, long long l, long long r) { l = nums[l], r = nums[r]; for(int i = 0; i < seg[k].Sum.size(); i++) { long long &R = seg[k].Sum[i]; R = 0; if(seg[2 * k + 1].LazyColor == -1) R += seg[2 * k + 1].Sum[i]; else if(seg[2 * k + 1].LazyColor == i) R += ((long long)(l + r) / 2LL - l) * seg[2 * k + 1].LazySum; if(seg[2 * k + 2].LazyColor == -1) R += seg[2 * k + 2].Sum[i]; else if(seg[2 * k + 2].LazyColor == i) R += (long long)(r - (l + r) / 2LL) * seg[2 * k + 2].LazySum; } } inline void Evaluation(int k, int l, int r) { if(seg[k].LazyColor == -1) return; if(k < sz - 1) { if(seg[2 * k + 1].LazyColor == seg[k].LazyColor) seg[2 * k + 1].LazySum += seg[k].LazySum; else seg[2 * k + 1].LazyColor = seg[k].LazyColor, seg[2 * k + 1].LazySum = seg[k].LazySum; if(seg[2 * k + 2].LazyColor == seg[k].LazyColor) seg[2 * k + 2].LazySum += seg[k].LazySum; else seg[2 * k + 2].LazyColor = seg[k].LazyColor, seg[2 * k + 2].LazySum = seg[k].LazySum; Update(k, l, r); } else { for(int i = 0; i < seg[k].Sum.size(); i++) { seg[k].Sum[i] = (seg[k].LazyColor == i) * seg[k].LazySum; } } seg[k].LazyColor = -1; seg[k].LazySum = 0; } inline void Write(int a, int b, int x, int k, int l, int r) { Evaluation(k, l, r); if(a >= r || b <= l) return; if(a <= l && r <= b) { if(seg[k].LazyColor == x) seg[k].LazySum++; else seg[k].LazyColor = x, seg[k].LazySum = 1; Evaluation(k, l, r); } else { Write(a, b, x, 2 * k + 1, l, l + r >> 1); Write(a, b, x, 2 * k + 2, l + r >> 1, r); Update(k, l, r); } } inline void Write(int a, int b, int k) { Write(a, b, k, 0, 0, sz); } inline vector< long long > CountSum(int a, int b, int k, int l, int r) { Evaluation(k, l, r); if(a >= r || b <= l) return(vector< long long >(5, 0LL)); if(a <= l && r <= b) return(seg[k].Sum); vector< long long > L = CountSum(a, b, 2 * k + 1, l, l + r >> 1); vector< long long > R = CountSum(a, b, 2 * k + 2, l + r >> 1, r); for(int i = 0; i < L.size(); i++) L[i] += R[i]; return(L); } inline vector< long long > CountSum(int a, int b) { return(CountSum(a, b, 0, 0, sz)); } }; int x[150000]; long long l[150000], r[150000]; int main() { int N, Q; scanf("%d", &N); scanf("%d", &Q); long long P[5] = {}; for(int i = 0; i < Q; i++) { scanf("%d %lld %lld", &x[i], &l[i], &r[i]); nums.push_back(l[i] - 1); nums.push_back(l[i]); nums.push_back(l[i] + 1); nums.push_back(r[i] - 1); nums.push_back(r[i]); nums.push_back(r[i] + 1); } sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); SegmentTree seg(nums.size()); for(int i = 0; i < Q; i++) { l[i] = lower_bound(nums.begin(), nums.end(), l[i]) - nums.begin(); r[i] = lower_bound(nums.begin(), nums.end(), r[i]) - nums.begin(); if(x[i] == 0) { vector< long long > Sum = seg.CountSum(l[i], r[i] + 1); vector< long long >::iterator Max = max_element(Sum.begin(), Sum.end()); if(count(Sum.begin(), Sum.end(), *Max) == 1) { (P[Max - Sum.begin()] += *Max) %= MOD; } } else if(x[i] >= 1) { seg.Write(l[i], r[i] + 1, x[i] - 1); } } vector< long long > Sum = seg.CountSum(0, nums.size()); for(int i = 0; i < 5; i++) { (P[i] += Sum[i]) %= MOD; if(i > 0) putchar(' '); printf("%lld", P[i]); } putchar('\n'); }