#include <bits/stdc++.h>
#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];

const int M = 2;

struct SegmentTree {
    int size;
    vector<ll> seg;
    vector<int> lazy; // -1: none, 1: set 0: reset
    SegmentTree(int n) {
        size = 1;	
        while (size < n) size *= 2;
        seg.resize(size * 2 - 1);
        lazy.resize(size * 2 - 1);
    }
    void evallazy(int k, int l, int r) {
    	if (lazy[k] == -1) return;
    	if (lazy[k]) {
    		seg[k] = wsum[r] - wsum[l];	
    	} else {
    		seg[k] = 0;
    	}
    	if (r - l > 1) {
    		lazy[k * 2 + 1] = lazy[k];
    		lazy[k * 2 + 2] = lazy[k];
    	}
    	lazy[k] = -1;
    }
    // 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) {
                lazy[k] = 1;
            } else {
            	lazy[k] = 0;
            }
            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);
            seg[k] = seg[k * 2 + 1] + seg[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 seg[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<class T1, class T2>
ostream &operator <<(ostream &os, const pair<T1, T2> &p) {
    cout << "(" << p.first << " " << p.second << ")";
}

template<class T>
ostream &operator <<(ostream &os, const vector<T> &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<ll> score(M);
        cout << score << endl;
        return 0;
    }
    vector<ll> 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

    vector<SegmentTree> segt(M, SegmentTree(w + 10));
    vector<ll> score(M);
    rep (i, Q) {
        if (x[i] == 0) {
            vector<pair<ll, ll>> t(M);
            rep (j, M) {
                t[j].second = j;
                t[j].first = segt[j].query(l[i], r[i] + 1);
            }
            sort(t.rbegin(), t.rend());
            if (t[0].first > t[1].first) {
                score[t[0].second] += t[0].first;
                score[t[0].second] %= mod;
            }
        } else {
            x[i]--;
            rep (j, M) {
                segt[j].update(l[i], r[i] + 1, x[i] != j);
            }
        }
    }

    rep (i, M) {
        score[i] += segt[i].query();
        score[i] %= mod;
    }

    cout << score << endl;

    return 0;
}