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

int n,m;
pair<int,int> p[100010];
int a[200010];
int b[200010];

int cmp(pair<int,int> q,pair<int,int> w)
{
	return q<w;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=m;i++) cin>>p[i].first>>p[i].second;
	sort(p+1,p+m+1,cmp);
	for (int i=1;i<=n;i++) a[i]=b[i]=i;
	for (int i=1;i<=m;i++) 
	{
		a[p[i].second]=min(a[p[i].second],a[p[i].second+1]);
		a[p[i].second+1]=min(a[p[i].second],a[p[i].second+1]);
		
		b[p[i].second]=max(b[p[i].second],b[p[i].second+1]);
		b[p[i].second+1]=max(b[p[i].second+1],b[p[i].second]);
	}
	cout<<b[1]-a[1]+1;
	for (int i=2;i<=n;i++) cout<<" "<<b[i]-a[i]+1;
	cout<<endl;
}
### Prompt

Create a solution in cpp for 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;

int n,m;
pair<int,int> p[100010];
int a[200010];
int b[200010];

int cmp(pair<int,int> q,pair<int,int> w)
{
	return q<w;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=m;i++) cin>>p[i].first>>p[i].second;
	sort(p+1,p+m+1,cmp);
	for (int i=1;i<=n;i++) a[i]=b[i]=i;
	for (int i=1;i<=m;i++) 
	{
		a[p[i].second]=min(a[p[i].second],a[p[i].second+1]);
		a[p[i].second+1]=min(a[p[i].second],a[p[i].second+1]);
		
		b[p[i].second]=max(b[p[i].second],b[p[i].second+1]);
		b[p[i].second+1]=max(b[p[i].second+1],b[p[i].second]);
	}
	cout<<b[1]-a[1]+1;
	for (int i=2;i<=n;i++) cout<<" "<<b[i]-a[i]+1;
	cout<<endl;
}
```