#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
int ud[2][200000];//ud[0][i]...iからスタートしたときに最も上に行ける(1は下)
P arm[100000];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		arm[i]=P(x,y);
	}
	sort(arm,arm+m);
	for(int i=0;i<n;i++)
	{
		ud[0][i]=i;
		ud[1][i]=i;
	}
	for(int i=0;i<m;i++)
	{
		ud[1][arm[i].second-1]=ud[1][arm[i].second];
		ud[0][arm[i].second]=ud[0][arm[i].second-1];
	}

	for(int i=0;i<n;i++)
	{
		cout<<ud[1][i]-ud[0][i]+1;
		if(i!=n-1)
			cout<<" ";
	}
	cout<<endl;
	return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 pair<int,int> P;
int ud[2][200000];//ud[0][i]...iからスタートしたときに最も上に行ける(1は下)
P arm[100000];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		arm[i]=P(x,y);
	}
	sort(arm,arm+m);
	for(int i=0;i<n;i++)
	{
		ud[0][i]=i;
		ud[1][i]=i;
	}
	for(int i=0;i<m;i++)
	{
		ud[1][arm[i].second-1]=ud[1][arm[i].second];
		ud[0][arm[i].second]=ud[0][arm[i].second-1];
	}

	for(int i=0;i<n;i++)
	{
		cout<<ud[1][i]-ud[0][i]+1;
		if(i!=n-1)
			cout<<" ";
	}
	cout<<endl;
	return 0;
}

```