#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define fs first
#define sc second

int main(){
	int n,m;
	while(cin>>n>>m){
		vector<pii> ud(n,pii(0,0));
		vector<pii> xy(m);
		rep(i,m) cin>>xy[i].fs>>xy[i].sc;
		sort(all(xy));
		for(auto p:xy){
			int i=p.sc;
			ud[i-1].sc=max(ud[i-1].sc,ud[i].sc+1);
			ud[i].fs=max(ud[i].fs,ud[i-1].fs+1);
		}
		rep(i,n){
			cout<<ud[i].fs+ud[i].sc+1;
			if(i+1==n) cout<<endl;
			else cout<<" ";
		}
	}
	return 0;
}


### Prompt

Please formulate 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;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define fs first
#define sc second

int main(){
	int n,m;
	while(cin>>n>>m){
		vector<pii> ud(n,pii(0,0));
		vector<pii> xy(m);
		rep(i,m) cin>>xy[i].fs>>xy[i].sc;
		sort(all(xy));
		for(auto p:xy){
			int i=p.sc;
			ud[i-1].sc=max(ud[i-1].sc,ud[i].sc+1);
			ud[i].fs=max(ud[i].fs,ud[i-1].fs+1);
		}
		rep(i,n){
			cout<<ud[i].fs+ud[i].sc+1;
			if(i+1==n) cout<<endl;
			else cout<<" ";
		}
	}
	return 0;
}


```