#include <bits/stdc++.h>
#define ALL(V) (V).begin(),(V).end()
#define ALLR(V) (V).rbegin(),(V).rend()
#define endl '\n'
using namespace std;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;
using TLL = tuple<ll, ll, ll>;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;

int main() {
    ll N, M;
    cin >> N >> M;
    V<PLL> xy(M);
    for(ll i = 0; i < M; i++) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        xy[i] = PLL(x, y);
    }

    sort(ALL(xy));
    V<PLL> ranges(N);
    for(ll i = 0; i < N; i++) ranges[i] = PLL(i, i + 1);

    for(auto &&ele : xy) {
        ll x, y;
        tie(x, y) = ele;
        ll a, b, c, d;
        tie(a, b) = ranges[y];
        tie(c, d) = ranges[y + 1];
        ranges[y] = ranges[y + 1] = PLL(min(a, c), max(b, d));
    }

    for(ll i = 0; i < N; i++) {
        ll x, y;
        tie(x, y) = ranges[i];
        cout << y - x << " \n"[i + 1 == N];
    }
    return 0;
}


### 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>
#define ALL(V) (V).begin(),(V).end()
#define ALLR(V) (V).rbegin(),(V).rend()
#define endl '\n'
using namespace std;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;
using TLL = tuple<ll, ll, ll>;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;

int main() {
    ll N, M;
    cin >> N >> M;
    V<PLL> xy(M);
    for(ll i = 0; i < M; i++) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        xy[i] = PLL(x, y);
    }

    sort(ALL(xy));
    V<PLL> ranges(N);
    for(ll i = 0; i < N; i++) ranges[i] = PLL(i, i + 1);

    for(auto &&ele : xy) {
        ll x, y;
        tie(x, y) = ele;
        ll a, b, c, d;
        tie(a, b) = ranges[y];
        tie(c, d) = ranges[y + 1];
        ranges[y] = ranges[y + 1] = PLL(min(a, c), max(b, d));
    }

    for(ll i = 0; i < N; i++) {
        ll x, y;
        tie(x, y) = ranges[i];
        cout << y - x << " \n"[i + 1 == N];
    }
    return 0;
}


```