OI XXXIII - des (Mle1)

// https://szkopul.edu.pl/problemset/problem/a0qKqyZmbnu2gCu_P8LSmKtV/site/?key=statement

// this code gets MLE
// 32/100 points

#include <bits/stdc++.h>

constexpr int sizik = 500 * 1001;

#define ar std::array

typedef std::pair<int, int> S;
typedef std::vector<S> P;
int n, m;

std::pair<S, bool> cr(const S& s1, const S& s2) {
    if (s1.first > s2.first) return cr(s2, s1);
    if (s2.first > s1.second) return {{}, false};
    if (s2.second <= s1.second) {
        return {s2, true};
    }
    return {{s2.first, s1.second}, true};
}

P merge(const P& a, const P& b) {
    if (a.size() > b.size()) {
        return merge(b, a);
    }
    const int n1 = a.size(), n2 = b.size();

    P ans;

    if (a.empty() || b.empty()) {
        return ans;
    }

    if (a[0].first == -1 && b[0].first == -1) {
        return ans;
    }
    if (a[0].first == -1) {
        return b;
    }
    if (b[0].first == -1) {
        return a;
    }

    int j = 0;
    for (int i = 0; i < n1; i++) {
        while (j < n2) {
            auto res = cr(a[i], b[j]);
            if (res.second) {
                ans.push_back(res.first);
                if (b[j].second > a[i].second) {
                    break;
                } else {
                    j++;
                }
            } else {
                if (b[j].first > a[i].first) {
                    break;
                } else {
                    j++;
                }
            }
        }
    }
    return ans;
}

P pg[sizik];

namespace sparse_table {

const int MAX_LOG = 20;
P st[MAX_LOG][sizik];
int lg[sizik];

void build(int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;

    for (int i = 1; i <= n; i++) {
        st[0][i] = pg[i];
    }

    for (int j = 1; j < MAX_LOG; j++) {
        int len = 1 << (j - 1);
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[j][i] = merge(st[j - 1][i], st[j - 1][i + len]);
        }
    }
}

P query(int L, int R) {
    if (L > R) return {{-1, -1}};

    int j = lg[R - L + 1];
    return merge(st[j][L], st[j][R - (1 << j) + 1]);
}

} // namespace sparse_table

void solve_b1() {
    std::cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int d, x, y;
        std::cin >> d >> x >> y;
        pg[d].push_back({x, y - 1});
    }
    for (int i = 1; i <= n; i++) {
        std::sort(pg[i].begin(), pg[i].end());
    }

    sparse_table::build(n);

    int x = 1;
    for (int i = 1; i <= n; i++) {
        if (x < i) x = i;

        P start = sparse_table::query(i, x);

        if (start.empty()) {
            std::cout << "0\n";
            continue;
        }
        int ans = x - i + 1;

        for (int j = x + 1; j <= n; j++) {
            start = merge(start, pg[j]);
            if (!start.empty()) {
                x = j;
                ans++;
            } else {
                break;
            }
        }
        std::cout << ans << '\n';
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    solve_b1();

    return 0;
}