#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<pair<int,int>> arms;
    for (int i=0;i<m;++i){
        int x,y; cin >> x >> y;
        arms.emplace_back(x,--y);
    }
    sort(arms.begin(),arms.end());
    vector<int> L(n),R(n);
    iota(L.begin(),L.end(),0);
    iota(R.begin(),R.end(),0);
    for (int i=0;i<m;++i){
        int y=arms[i].second;
        L[y+1]=L[y]; R[y]=R[y+1];
    }
    for (int i=0;i<n;++i) cout << R[i]-L[i]+1 << (i+1==n?'\n':' ');
}

### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<pair<int,int>> arms;
    for (int i=0;i<m;++i){
        int x,y; cin >> x >> y;
        arms.emplace_back(x,--y);
    }
    sort(arms.begin(),arms.end());
    vector<int> L(n),R(n);
    iota(L.begin(),L.end(),0);
    iota(R.begin(),R.end(),0);
    for (int i=0;i<m;++i){
        int y=arms[i].second;
        L[y+1]=L[y]; R[y]=R[y+1];
    }
    for (int i=0;i<n;++i) cout << R[i]-L[i]+1 << (i+1==n?'\n':' ');
}

```