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

pair<int,int> merge(pair<int,int> l,pair<int,int> r){return {l.first,r.second};}

int main(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>> xy(m);
  for(int i=0;i<m;i++) {
    cin>>xy[i].first>>xy[i].second;
    xy[i].second--;
  }

  sort(xy.begin(),xy.end());
  vector<pair<int,int>> range(n);
  for(int i=0;i<n;i++) range[i]={i,i};
  
  for(int i=0;i<m;i++){
    range[xy[i].second]=range[xy[i].second+1]=merge(range[xy[i].second],range[xy[i].second+1]);
  }

  for(int i=0;i<n;i++){
    cout<<range[i].second-range[i].first+1;
    if(i!=n-1) cout<<" ";
    else cout<<endl;
  }
				   
  return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

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

pair<int,int> merge(pair<int,int> l,pair<int,int> r){return {l.first,r.second};}

int main(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>> xy(m);
  for(int i=0;i<m;i++) {
    cin>>xy[i].first>>xy[i].second;
    xy[i].second--;
  }

  sort(xy.begin(),xy.end());
  vector<pair<int,int>> range(n);
  for(int i=0;i<n;i++) range[i]={i,i};
  
  for(int i=0;i<m;i++){
    range[xy[i].second]=range[xy[i].second+1]=merge(range[xy[i].second],range[xy[i].second+1]);
  }

  for(int i=0;i<n;i++){
    cout<<range[i].second-range[i].first+1;
    if(i!=n-1) cout<<" ";
    else cout<<endl;
  }
				   
  return 0;
}
```