#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define rep1(i,N) for(int i=1;i<=(int)N;i++)
#define pb push_back
#define all(c) c.begin(),c.end()
#define fs first
#define sc second
#define show(x) cout<<#x<<" "<<x<<endl
using namespace std;
int N,M;
typedef pair<int,int> P;
int x[100000],y[100000];
P ps[100000];
set<int> y2xs[200000];
int udp[200010],ddp[200010];
vector<int> xs;
int main(){
	cin>>N>>M;
	rep(i,M) cin>>x[i]>>y[i];
	rep(i,M) xs.pb(x[i]);
	sort(all(xs));
	rep(i,M) x[i]=lower_bound(all(xs),x[i])-xs.begin();
	rep(i,M){
		y[i]--;
		ps[i]=P(x[i],y[i]);
		y2xs[y[i]].insert(x[i]);
	}
	sort(ps,ps+M);
	rep(i,M) x[i]=ps[i].fs,y[i]=ps[i].sc;
	rep(i,M){	//goup
		int X=x[i],Y=y[i];
		if(Y==0){
			udp[i]=0;
		}else{
			auto it=y2xs[Y-1].lower_bound(X);
			if(it==y2xs[Y-1].begin()){
				udp[i]=Y;
			}else{
				it--;
				udp[i]=udp[*it];
			}
		}
	}
	rep(i,M){	//godwn
		int X=x[i],Y=y[i];
		if(Y==N-2){
			ddp[i]=N-1;
		}else{
			auto it=y2xs[Y+1].lower_bound(X);
			if(it==y2xs[Y+1].begin()){
				ddp[i]=Y+1;
			}else{
				it--;
				ddp[i]=ddp[*it];
			}
		}
	}
	rep(y,N){
		int u;
		if(y==0) u=0;
		else if(y2xs[y-1].empty()) u=y;
		else u=udp[*y2xs[y-1].rbegin()];

		int d;
		if(y==N-1) d=N-1;
		else if(y2xs[y].empty()) d=y;
		else d=ddp[*y2xs[y].rbegin()];

//		cout<<u<<"  "<<d<<endl;

		cout<<d-u+1<<(y==N-1?"\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>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define rep1(i,N) for(int i=1;i<=(int)N;i++)
#define pb push_back
#define all(c) c.begin(),c.end()
#define fs first
#define sc second
#define show(x) cout<<#x<<" "<<x<<endl
using namespace std;
int N,M;
typedef pair<int,int> P;
int x[100000],y[100000];
P ps[100000];
set<int> y2xs[200000];
int udp[200010],ddp[200010];
vector<int> xs;
int main(){
	cin>>N>>M;
	rep(i,M) cin>>x[i]>>y[i];
	rep(i,M) xs.pb(x[i]);
	sort(all(xs));
	rep(i,M) x[i]=lower_bound(all(xs),x[i])-xs.begin();
	rep(i,M){
		y[i]--;
		ps[i]=P(x[i],y[i]);
		y2xs[y[i]].insert(x[i]);
	}
	sort(ps,ps+M);
	rep(i,M) x[i]=ps[i].fs,y[i]=ps[i].sc;
	rep(i,M){	//goup
		int X=x[i],Y=y[i];
		if(Y==0){
			udp[i]=0;
		}else{
			auto it=y2xs[Y-1].lower_bound(X);
			if(it==y2xs[Y-1].begin()){
				udp[i]=Y;
			}else{
				it--;
				udp[i]=udp[*it];
			}
		}
	}
	rep(i,M){	//godwn
		int X=x[i],Y=y[i];
		if(Y==N-2){
			ddp[i]=N-1;
		}else{
			auto it=y2xs[Y+1].lower_bound(X);
			if(it==y2xs[Y+1].begin()){
				ddp[i]=Y+1;
			}else{
				it--;
				ddp[i]=ddp[*it];
			}
		}
	}
	rep(y,N){
		int u;
		if(y==0) u=0;
		else if(y2xs[y-1].empty()) u=y;
		else u=udp[*y2xs[y-1].rbegin()];

		int d;
		if(y==N-1) d=N-1;
		else if(y2xs[y].empty()) d=y;
		else d=ddp[*y2xs[y].rbegin()];

//		cout<<u<<"  "<<d<<endl;

		cout<<d-u+1<<(y==N-1?"\n":" ");
	}
}
```