#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>::iterator I;
int main(){
  int n,m;cin>>n>>m;
  vector<int> v[n];
  for(int i=0;i<m;i++){
    int x,y;cin>>x>>y;
    v[y].push_back(-x);
  }
  for(int i=0;i<n;i++) sort(v[i].begin(),v[i].end());
  map<I,int> m1,m2;
  vector<I> vi;
  for(int i=0;i<n;i++){
    int t=i,b=i+1,p=-100000;
    vi.clear();
    while(1){
      if(t==0) break;
      I it = lower_bound(v[t].begin(),v[t].end(),p);
      if(it==v[t].end()) break;
      if(m1.find(it)!=m1.end()){
	t=m1[it];
	break;
      }
      p=*it;t--;
      vi.push_back(it);
    }
    for(int j=0;j<(int)vi.size();j++) m1[vi[j]]=t;
    vi.clear();
    p=-100000;
    while(1){
      if(b==n) break;
      I it = lower_bound(v[b].begin(),v[b].end(),p);
      if(it==v[b].end()) break;
      if(m2.find(it)!=m2.end()){
	b=m2[it];
	break;
      }
      p=*it;b++;
      vi.push_back(it);
    }
    for(int j=0;j<(int)vi.size();j++) m2[vi[j]]=b;
    cout << b-t << " \n"[i==n-1];
  }
  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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>::iterator I;
int main(){
  int n,m;cin>>n>>m;
  vector<int> v[n];
  for(int i=0;i<m;i++){
    int x,y;cin>>x>>y;
    v[y].push_back(-x);
  }
  for(int i=0;i<n;i++) sort(v[i].begin(),v[i].end());
  map<I,int> m1,m2;
  vector<I> vi;
  for(int i=0;i<n;i++){
    int t=i,b=i+1,p=-100000;
    vi.clear();
    while(1){
      if(t==0) break;
      I it = lower_bound(v[t].begin(),v[t].end(),p);
      if(it==v[t].end()) break;
      if(m1.find(it)!=m1.end()){
	t=m1[it];
	break;
      }
      p=*it;t--;
      vi.push_back(it);
    }
    for(int j=0;j<(int)vi.size();j++) m1[vi[j]]=t;
    vi.clear();
    p=-100000;
    while(1){
      if(b==n) break;
      I it = lower_bound(v[b].begin(),v[b].end(),p);
      if(it==v[b].end()) break;
      if(m2.find(it)!=m2.end()){
	b=m2[it];
	break;
      }
      p=*it;b++;
      vi.push_back(it);
    }
    for(int j=0;j<(int)vi.size();j++) m2[vi[j]]=b;
    cout << b-t << " \n"[i==n-1];
  }
  return 0;
}
```