#include <iostream>
#include <algorithm>
#include <map>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef pair<int,int> P;

int n, m;
P arm[100000];
int st[200000];
int en[200000];

void init(){
    rep(i,n){
        st[i] = i;
        en[i] = i+1;
    }
}

void unite(int x, int y){
    int s = min(st[x],st[y]);
    int e = max(en[x],en[y]);
    st[x] = s; st[y] = s;
    en[x] = e; en[y] = e;
}

int main(){
    cin >> n >> m;
    init();
    rep(i,m){
        int x, y;
        cin >> x >> y;
        arm[i] = P(x,y);
    }
    sort(arm,arm+m);
    rep(i,m){
        unite(arm[i].second-1,arm[i].second);
    }
    rep(i,n){
        if(i != n-1) cout << en[i]-st[i] << " ";
        else cout << en[i]-st[i] << endl;
    }
}
### Prompt

Your task is to create a Cpp solution to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <iostream>
#include <algorithm>
#include <map>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef pair<int,int> P;

int n, m;
P arm[100000];
int st[200000];
int en[200000];

void init(){
    rep(i,n){
        st[i] = i;
        en[i] = i+1;
    }
}

void unite(int x, int y){
    int s = min(st[x],st[y]);
    int e = max(en[x],en[y]);
    st[x] = s; st[y] = s;
    en[x] = e; en[y] = e;
}

int main(){
    cin >> n >> m;
    init();
    rep(i,m){
        int x, y;
        cin >> x >> y;
        arm[i] = P(x,y);
    }
    sort(arm,arm+m);
    rep(i,m){
        unite(arm[i].second-1,arm[i].second);
    }
    rep(i,n){
        if(i != n-1) cout << en[i]-st[i] << " ";
        else cout << en[i]-st[i] << endl;
    }
}
```