#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
	int n,m;
	cin>>n>>m;
	int d[222222]={};
	int u[222222]={};
	vector<P> v;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		v.push_back(P(x,y));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++){
		int t=v[i].second;
		d[t+1]=d[t]+1;
		u[t]=u[t+1]+1;
	}
	for(int i=1;i<=n;i++){
		if(i-1)cout<<" ";
		cout<<d[i]+u[i]+1;
		//cout<<d[i]<<" "<<u[i]<<endl;
	}
	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 main(){
	int n,m;
	cin>>n>>m;
	int d[222222]={};
	int u[222222]={};
	vector<P> v;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		v.push_back(P(x,y));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++){
		int t=v[i].second;
		d[t+1]=d[t]+1;
		u[t]=u[t+1]+1;
	}
	for(int i=1;i<=n;i++){
		if(i-1)cout<<" ";
		cout<<d[i]+u[i]+1;
		//cout<<d[i]<<" "<<u[i]<<endl;
	}
	cout<<endl;
	return 0;
}


```