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

typedef pair<int,int> P;

P merge(P a,P b){
  int left=min(a.first,b.first);
  int right=max(a.second,b.second);
  return P(left,right);
}

int n,m;

vector<int> G[200005];

P ans[200005];

int main(){
  scanf("%d %d",&n,&m);

  for(int i=0;i<m;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    G[x].push_back(y);
  }

  for(int i=0;i<n;i++){
    ans[i]=P(i,i);
  }

  for(int x=0;x<100005;x++){
    for(int i=0;i<(int)G[x].size();i++){
      int y=G[x][i];
      ans[y] = ans[y-1] = merge(ans[y],ans[y-1]);
    }
  }

  for(int i=0;i<n;i++){
    if(i)printf(" ");
    printf("%d",ans[i].second-ans[i].first+1);
  }
  printf("\n");
  return 0;
}
### 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 pair<int,int> P;

P merge(P a,P b){
  int left=min(a.first,b.first);
  int right=max(a.second,b.second);
  return P(left,right);
}

int n,m;

vector<int> G[200005];

P ans[200005];

int main(){
  scanf("%d %d",&n,&m);

  for(int i=0;i<m;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    G[x].push_back(y);
  }

  for(int i=0;i<n;i++){
    ans[i]=P(i,i);
  }

  for(int x=0;x<100005;x++){
    for(int i=0;i<(int)G[x].size();i++){
      int y=G[x][i];
      ans[y] = ans[y-1] = merge(ans[y],ans[y-1]);
    }
  }

  for(int i=0;i<n;i++){
    if(i)printf(" ");
    printf("%d",ans[i].second-ans[i].first+1);
  }
  printf("\n");
  return 0;
}
```