#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define MIN(a,b) (((a)>(b))?(b):(a))
#define MAX(a,b) (((a)<(b))?(b):(a))
using namespace std;

typedef pair<int,int> pii;

int main(void){
	int n,m,a,b;
	int l[200000],r[200000];
	std::vector<pii> v;
	cin>>n>>m;
	for(int i=0;i<n;i++)l[i]=r[i]=i;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		v.push_back(make_pair(a,b-1));
	}
	std::sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		int lane=v[i].second;
		l[lane]=MIN(l[lane+1],l[lane]);
		r[lane]=MAX(r[lane+1],r[lane]);
		l[lane+1]=MIN(l[lane],l[lane+1]);
		r[lane+1]=MAX(r[lane],r[lane+1]);
		// cout<<"---"<<i<<"---"<<endl;
		// for(int j=0;j<n;j++){
			// cout<<l[j]<<" "<<r[j]<<endl;
		// }
	}

	for(int i=0;i<n;i++){
		if(i!=n-1)cout<<r[i]-l[i]+1<<" ";
		else cout<<r[i]-l[i]+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 <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define MIN(a,b) (((a)>(b))?(b):(a))
#define MAX(a,b) (((a)<(b))?(b):(a))
using namespace std;

typedef pair<int,int> pii;

int main(void){
	int n,m,a,b;
	int l[200000],r[200000];
	std::vector<pii> v;
	cin>>n>>m;
	for(int i=0;i<n;i++)l[i]=r[i]=i;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		v.push_back(make_pair(a,b-1));
	}
	std::sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		int lane=v[i].second;
		l[lane]=MIN(l[lane+1],l[lane]);
		r[lane]=MAX(r[lane+1],r[lane]);
		l[lane+1]=MIN(l[lane],l[lane+1]);
		r[lane+1]=MAX(r[lane],r[lane+1]);
		// cout<<"---"<<i<<"---"<<endl;
		// for(int j=0;j<n;j++){
			// cout<<l[j]<<" "<<r[j]<<endl;
		// }
	}

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

	return 0;
}
```