#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
pair<int,int>a[1<<17];
int L[2<<17],R[2<<17];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)L[i]=R[i]=i;
	L[n]=R[n]=n-1;
	for(int i=0;i<m;i++)
	{
		cin>>a[i].first>>a[i].second;
	}
	sort(a,a+m);
	for(int i=0;i<m;i++)
	{
		L[a[i].second]=L[a[i].second-1];
		R[a[i].second-1]=R[a[i].second];
	}
	for(int i=0;i<n;i++)
	{
		cout<<R[i]-L[i]+1<<(i==n-1?"\n":" ");
	}
}


### Prompt

Your challenge is to write 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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
pair<int,int>a[1<<17];
int L[2<<17],R[2<<17];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)L[i]=R[i]=i;
	L[n]=R[n]=n-1;
	for(int i=0;i<m;i++)
	{
		cin>>a[i].first>>a[i].second;
	}
	sort(a,a+m);
	for(int i=0;i<m;i++)
	{
		L[a[i].second]=L[a[i].second-1];
		R[a[i].second-1]=R[a[i].second];
	}
	for(int i=0;i<n;i++)
	{
		cout<<R[i]-L[i]+1<<(i==n-1?"\n":" ");
	}
}


```