#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include #define getchar getchar_unlocked #define putchar putchar_unlocked int64_t in() { int64_t n; int c; while ((c = getchar()) < '0') if (c == EOF) return -1; n = c - '0'; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } struct node { int64_t sum[5]; int64_t w; int fill; int thick; bool reset; }; const int64_t mod = int64_t(1e18) + 9; const int H = 19; const int N = 1 << H; const int Q = 150000; int q; int64_t n, X[Q], L[Q], R[Q], dict[Q * 2], sum[5], result[5]; node ns[N * 2]; void set_lazy(int k, int c, int thick, bool reset) { if (ns[k].thick > 0 && ns[k].fill != c) reset = true; int64_t s = ns[k].sum[c]; memset(ns[k].sum, 0, sizeof(ns[k].sum)); if (reset) { ns[k].thick = 0; ns[k].reset = true; s = 0; } ns[k].thick += thick; ns[k].fill = c; ns[k].sum[c] = thick * ns[k].w + s; } void push(int k) { if (ns[k].thick == 0) return; set_lazy(k * 2 + 0, ns[k].fill, ns[k].thick, ns[k].reset); set_lazy(k * 2 + 1, ns[k].fill, ns[k].thick, ns[k].reset); ns[k].fill = -1; ns[k].thick = 0; ns[k].reset = false; } void fix(int k) { for (int i = 0; i < 5; i++) { ns[k].sum[i] = ns[k * 2].sum[i] + ns[k * 2 + 1].sum[i]; } } void add(int k) { for (int i = 0; i < 5; i++) result[i] += ns[k].sum[i]; } void push_sup(int l, int r) { for (int i = H; i >= 1; i--) { push(l >> i); push(r >> i); } } void update(int l, int r, int c) { l += N; r += N; int X = l & -l; int Y = r & -r; int ll = l / X; int rr = r / Y - 1; push_sup(l, r - 1); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) set_lazy(l++, c, 1, false); if (r & 1) set_lazy(--r, c, 1, false); } if (X > Y) std::swap(X, Y), std::swap(ll, rr); for (; X < Y; X <<= 1, ll >>= 1) fix(ll >> 1); for (; ll != rr; ll >>= 1, rr >>= 1) { fix(ll >> 1); fix(rr >> 1); } for (; ll > 1; ll >>= 1) fix(ll >> 1); } void query(int l, int r) { l += N; r += N; push_sup(l, r - 1); memset(result, 0, sizeof(result)); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) add(l++); if (r & 1) add(--r); } } int main() { n = in(), q = in(); for (int i = 0; i < q; i++) { X[i] = in() - 1, L[i] = in(), R[i] = in() + 1; dict[i * 2 + 0] = L[i]; dict[i * 2 + 1] = R[i]; } std::sort(dict, dict + q * 2); int m = std::unique(dict, dict + q * 2) - dict; for (int i = 0; i < m - 1; i++) ns[i + N].w = dict[i + 1] - dict[i]; for (int i = N - 1; i >= 1; i--) ns[i].w = ns[i * 2].w + ns[i * 2 + 1].w; for (int i = 0; i < q; i++) { L[i] = std::lower_bound(dict, dict + m, L[i]) - dict; R[i] = std::lower_bound(dict, dict + m, R[i]) - dict; if (X[i] == -1) { query(L[i], R[i]); int id = std::max_element(result, result + 5) - result; for (int j = 0; j < 5; j++) { if (j != id && result[j] == result[id]) { id = -1; break; } } if (id >= 0) (sum[id] += result[id]) %= mod; } else { update(L[i], R[i], X[i]); } } for (int i = 0; i < 5; i++) printf("%lld ", (ns[1].sum[i] + sum[i]) % mod); }