#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
using namespace std;
using P = pair<int,int>;

int main(){
    int n,m;
    cin>>n>>m;
    vector<P> V;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        V.emplace_back(x-1,y-1);
    }
    sort(V.begin(), V.end());
    int lb[n],ub[n];
    for(int i=0;i<n;i++) lb[i]=ub[i]=i;
    for(auto p:V){
        int x,y;
        tie(x,y)=p;
        lb[y]=lb[y+1]=min(lb[y],lb[y+1]);
        ub[y]=ub[y+1]=max(ub[y],ub[y+1]);
    }
    for(int i=0;i<n;i++){
        if(i)cout<<' ';
        cout<<ub[i]-lb[i]+1;
    }
    cout<<endl;

    return 0;
}
### Prompt

Please formulate 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 <tuple>
#include <algorithm>
#include <vector>
using namespace std;
using P = pair<int,int>;

int main(){
    int n,m;
    cin>>n>>m;
    vector<P> V;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        V.emplace_back(x-1,y-1);
    }
    sort(V.begin(), V.end());
    int lb[n],ub[n];
    for(int i=0;i<n;i++) lb[i]=ub[i]=i;
    for(auto p:V){
        int x,y;
        tie(x,y)=p;
        lb[y]=lb[y+1]=min(lb[y],lb[y+1]);
        ub[y]=ub[y+1]=max(ub[y],ub[y+1]);
    }
    for(int i=0;i<n;i++){
        if(i)cout<<' ';
        cout<<ub[i]-lb[i]+1;
    }
    cout<<endl;

    return 0;
}
```