#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max()/2;
const int MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;
    vector<P> v(m);
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        v[i]=P(x,y);
    }
    vector<P> w(n+1);
    for(int i=1;i<=n;i++){
        w[i]=P(i,i);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<m;i++){
        int y=v[i].second;
        w[y].second=w[y+1].second;
        w[y+1].first=w[y].first;
    }
    for(int i=1;i<=n;i++){
        int res=w[i].second-w[i].first+1;
        if(i==1) cout<<res;
        else cout<<" "<<res;
    }
    cout<<endl;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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<int,int> P;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max()/2;
const int MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;
    vector<P> v(m);
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        v[i]=P(x,y);
    }
    vector<P> w(n+1);
    for(int i=1;i<=n;i++){
        w[i]=P(i,i);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<m;i++){
        int y=v[i].second;
        w[y].second=w[y+1].second;
        w[y+1].first=w[y].first;
    }
    for(int i=1;i<=n;i++){
        int res=w[i].second-w[i].first+1;
        if(i==1) cout<<res;
        else cout<<" "<<res;
    }
    cout<<endl;
}

```