#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class SegmentManager {
    ll len;
    set<P> s;
    ll length(const P& p) {
        return p.second - p.first;
    }
    set<P>::iterator erase(const set<P>::iterator it) {
        len -= length(*it);
        return s.erase(it);
    }
    void insert(const P& p) {
        len += length(p);
        s.insert(p);
    }
    set<P>::iterator lb(ll l) {
        return s.lower_bound({l, l});
    }
    set<P>::iterator ub(ll l) {
        return lb(l+1);
    }
public:
    SegmentManager() : len(0) {}
    set<P> getset() {
        return s;
    }
    void add(ll l, ll r) {
        if (r <= l) return;
        erase(l, r);
        // merge right
        {
            auto it = lb(r);
            if (it != s.end() && it->first == r) {
                r = it->second;
                erase(it);
            }
        }
        // merge left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second == l) {
                    l = it->first;
                    erase(it);
                }
            }
        }
        // add
        insert({l, r});
    }
    void erase(ll l, ll r) {
        if (r <= l) return;
        // cut left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second > l) {
                    insert({it->first, l});
                    if (it->second > r) {
                        insert({r, it->second});
                        erase(it);
                        return;
                    }
                    erase(it);
                }
            }
        }
        auto it = lb(l);
        auto itr = lb(r);
        while (it != itr) {
            if (it->second > r) {
                insert({r, it->second});
                it = erase(it);
                break;
            }
            it = erase(it);
        }
    }
    bool is_in(ll l, ll r) {
        assert(r >= l);
        auto it = ub(l);
        if (it == s.begin()) return false;
        --it;
        return it->first <= l && r <= it->second;
    }
    bool is_in(ll pos) { return is_in(pos, pos+1); }
    ll length() { return len; }
    ll count() { return s.size(); }
    void out() {
        each(p, s) {
            cout << "[" << p.first << ", " << p.second << ")" << endl;
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m; cin >> n >> m;
    vector<P> crane;
    rep(i, m) {
        ll x, y; cin >> x >> y;
        crane.pb({x, y-1});
    }
    sort(all(crane));
    // vector<ll> l(n), r(n);
    // rep(i, n) l[i] = i, r[i] = i+1;
    // each(p, crane) {
    //     ll i = p.second;
    //     l[i] = l[i+1] = min(l[i], l[i+1]);
    //     r[i] = r[i+1] = max(r[i], r[i+1]);
    // }
    vector<SegmentManager> sm(n);
    rep(i, n) sm[i].add(i, i+1);
    each(p, crane) {
        ll pos = p.second;
        each(pp, sm[pos+1].getset()) {
            sm[pos].add(pp.first, pp.second);
        }
        sm[pos+1] = sm[pos];
    }
    vector<ll> ans;
    // rep(i, n) ans.pb(r[i]-l[i]);
    rep(i, n) ans.pb(sm[i].length());
    cout << ans << endl;
}
### Prompt

In Cpp, your task is to solve the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class SegmentManager {
    ll len;
    set<P> s;
    ll length(const P& p) {
        return p.second - p.first;
    }
    set<P>::iterator erase(const set<P>::iterator it) {
        len -= length(*it);
        return s.erase(it);
    }
    void insert(const P& p) {
        len += length(p);
        s.insert(p);
    }
    set<P>::iterator lb(ll l) {
        return s.lower_bound({l, l});
    }
    set<P>::iterator ub(ll l) {
        return lb(l+1);
    }
public:
    SegmentManager() : len(0) {}
    set<P> getset() {
        return s;
    }
    void add(ll l, ll r) {
        if (r <= l) return;
        erase(l, r);
        // merge right
        {
            auto it = lb(r);
            if (it != s.end() && it->first == r) {
                r = it->second;
                erase(it);
            }
        }
        // merge left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second == l) {
                    l = it->first;
                    erase(it);
                }
            }
        }
        // add
        insert({l, r});
    }
    void erase(ll l, ll r) {
        if (r <= l) return;
        // cut left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second > l) {
                    insert({it->first, l});
                    if (it->second > r) {
                        insert({r, it->second});
                        erase(it);
                        return;
                    }
                    erase(it);
                }
            }
        }
        auto it = lb(l);
        auto itr = lb(r);
        while (it != itr) {
            if (it->second > r) {
                insert({r, it->second});
                it = erase(it);
                break;
            }
            it = erase(it);
        }
    }
    bool is_in(ll l, ll r) {
        assert(r >= l);
        auto it = ub(l);
        if (it == s.begin()) return false;
        --it;
        return it->first <= l && r <= it->second;
    }
    bool is_in(ll pos) { return is_in(pos, pos+1); }
    ll length() { return len; }
    ll count() { return s.size(); }
    void out() {
        each(p, s) {
            cout << "[" << p.first << ", " << p.second << ")" << endl;
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m; cin >> n >> m;
    vector<P> crane;
    rep(i, m) {
        ll x, y; cin >> x >> y;
        crane.pb({x, y-1});
    }
    sort(all(crane));
    // vector<ll> l(n), r(n);
    // rep(i, n) l[i] = i, r[i] = i+1;
    // each(p, crane) {
    //     ll i = p.second;
    //     l[i] = l[i+1] = min(l[i], l[i+1]);
    //     r[i] = r[i+1] = max(r[i], r[i+1]);
    // }
    vector<SegmentManager> sm(n);
    rep(i, n) sm[i].add(i, i+1);
    each(p, crane) {
        ll pos = p.second;
        each(pp, sm[pos+1].getset()) {
            sm[pos].add(pp.first, pp.second);
        }
        sm[pos+1] = sm[pos];
    }
    vector<ll> ans;
    // rep(i, n) ans.pb(r[i]-l[i]);
    rep(i, n) ans.pb(sm[i].length());
    cout << ans << endl;
}
```