#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#define rint register int
using namespace std;
inline void read(int &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	x*=f;
}
const int maxn=200003,maxm=100003;
int x[maxm],p[maxm],n,m,dp[maxm],ans[maxn];
vector<int> a[maxn],id[maxn];
#define pb push_back
int main() {
	read(n);read(m);int tot=0;
	for(rint i=1;i<=m;++i) {
		read(x[i]);read(p[i]);
		a[p[i]].pb(x[i]);
	}
	for(rint i=1;i<n;++i) if(!a[i].empty()) {
		sort(a[i].begin(),a[i].end());
		for(auto x:a[i]) id[i].pb(++tot);
	}
	ans[1]=1;
	for(rint i=2;i<=n;++i) {
		int sz=a[i-1].size(),mx=1;
		for(rint j=0;j<sz;++j) {
			auto k=upper_bound(a[i-2].begin(),a[i-2].end(),a[i-1][j])-1;
			if(a[i-2].empty()||k<a[i-2].begin()) {dp[id[i-1][j]]=2;mx=max(mx,dp[id[i-1][j]]);continue;}
			dp[id[i-1][j]]=dp[id[i-2][k-a[i-2].begin()]]+1;
			mx=max(mx,dp[id[i-1][j]]);
		}
		ans[i]=mx;
	}
	memset(dp,0,sizeof dp);
	for(rint i=n-1;i>=1;--i) {
		int sz=a[i].size(),mx=1;
		for(rint j=0;j<sz;++j) {
			auto k=upper_bound(a[i+1].begin(),a[i+1].end(),a[i][j])-1;
			if(a[i+1].empty()||k<a[i+1].begin()) {dp[id[i][j]]=2;mx=max(mx,dp[id[i][j]]);continue;}
			dp[id[i][j]]=dp[id[i+1][k-a[i+1].begin()]]+1;
			mx=max(mx,dp[id[i][j]]);
		}
		ans[i]+=mx-1;
	}
	for(rint i=1;i<n;++i)	printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
	return 0;
}
 

### 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<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#define rint register int
using namespace std;
inline void read(int &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	x*=f;
}
const int maxn=200003,maxm=100003;
int x[maxm],p[maxm],n,m,dp[maxm],ans[maxn];
vector<int> a[maxn],id[maxn];
#define pb push_back
int main() {
	read(n);read(m);int tot=0;
	for(rint i=1;i<=m;++i) {
		read(x[i]);read(p[i]);
		a[p[i]].pb(x[i]);
	}
	for(rint i=1;i<n;++i) if(!a[i].empty()) {
		sort(a[i].begin(),a[i].end());
		for(auto x:a[i]) id[i].pb(++tot);
	}
	ans[1]=1;
	for(rint i=2;i<=n;++i) {
		int sz=a[i-1].size(),mx=1;
		for(rint j=0;j<sz;++j) {
			auto k=upper_bound(a[i-2].begin(),a[i-2].end(),a[i-1][j])-1;
			if(a[i-2].empty()||k<a[i-2].begin()) {dp[id[i-1][j]]=2;mx=max(mx,dp[id[i-1][j]]);continue;}
			dp[id[i-1][j]]=dp[id[i-2][k-a[i-2].begin()]]+1;
			mx=max(mx,dp[id[i-1][j]]);
		}
		ans[i]=mx;
	}
	memset(dp,0,sizeof dp);
	for(rint i=n-1;i>=1;--i) {
		int sz=a[i].size(),mx=1;
		for(rint j=0;j<sz;++j) {
			auto k=upper_bound(a[i+1].begin(),a[i+1].end(),a[i][j])-1;
			if(a[i+1].empty()||k<a[i+1].begin()) {dp[id[i][j]]=2;mx=max(mx,dp[id[i][j]]);continue;}
			dp[id[i][j]]=dp[id[i+1][k-a[i+1].begin()]]+1;
			mx=max(mx,dp[id[i][j]]);
		}
		ans[i]+=mx-1;
	}
	for(rint i=1;i<n;++i)	printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
	return 0;
}
 

```