#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> mypair;

int main(){
	int n,m;
	cin>>n>>m;
	vector<mypair> now(n+1);
	for(int i=0;i<=n;i++)now[i] = mypair(i,i);
	priority_queue<mypair,vector<mypair> ,greater<mypair> > q;
	for(int i=0;i<m;i++){
	int x,y;
	cin>>x>>y;
	q.push( mypair(x,y) );
	}
	while(!q.empty()){
	int y = q.top().second;
	q.pop();
	mypair tmp = mypair(now[y].first,now[y+1].second);
	now[y] = tmp;
	now[y+1] = tmp;
	}
	for(int i=1;i<n;i++)cout<<now[i].second-now[i].first+1<<' ';
	cout<<now[n].second-now[n].first+1<<endl;

		return 0;
}


### Prompt

Your task is to create 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>
using namespace std;
typedef pair<int,int> mypair;

int main(){
	int n,m;
	cin>>n>>m;
	vector<mypair> now(n+1);
	for(int i=0;i<=n;i++)now[i] = mypair(i,i);
	priority_queue<mypair,vector<mypair> ,greater<mypair> > q;
	for(int i=0;i<m;i++){
	int x,y;
	cin>>x>>y;
	q.push( mypair(x,y) );
	}
	while(!q.empty()){
	int y = q.top().second;
	q.pop();
	mypair tmp = mypair(now[y].first,now[y+1].second);
	now[y] = tmp;
	now[y+1] = tmp;
	}
	for(int i=1;i<n;i++)cout<<now[i].second-now[i].first+1<<' ';
	cout<<now[n].second-now[n].first+1<<endl;

		return 0;
}


```