#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;


int main(){
	int n,m;
	cin >> n >> m;
	
	vector<pair<int,int> > arm(m);
	for(int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		arm[i]=make_pair(y,x);
	}
	sort(arm.begin(), arm.end());
	
	vector<int> lb(n+1, 1e9);
	vector<bool> used(m, false);
	for(int i=1; i<=n; i++){
		int lane=i;
		int position=0;
		while(1){
			vector<pair<int,int> >::iterator it;
			it = lower_bound(arm.begin(), arm.end(), make_pair(lane, position));
			if(it == arm.end() || it->first!=lane || used[it-arm.begin()]){
				lb[lane] = min(i, lb[lane]);
				break;
			}
			
			used[it-arm.begin()] = true;
			lb[lane] = min(i, lb[lane]);
			lane++;
			position = it->second;
		}
	}
	
	for(int i=0; i<m; i++){
		arm[i].first = -arm[i].first;
		used[i]=false;
	}
	sort(arm.begin(), arm.end());
	vector<int> ub(n+1, 0);
	for(int i=n; i>0; i--){
		int lane=i;
		int position=0;
		while(1){
			vector<pair<int,int> >::iterator it;
			it = lower_bound(arm.begin(), arm.end(), make_pair(-(lane-1), position));
			if(it == arm.end() || it->first!=-(lane-1)|| used[it-arm.begin()]){
				ub[lane] = max(i, ub[lane]);
				break;
			}
			
			used[it-arm.begin()] = true;
			ub[lane] = max(i, ub[lane]);
			lane--;
			position = it->second;
		}
	}
	
	for(int i=1; i<n; i++){
		cout << ub[i]-lb[i]+1 << " ";
	}
	cout << ub[n]-lb[n]+1 << endl;
	
	return 0;
}
### Prompt

Your challenge is to write 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 <algorithm>
#include <cmath>
#include <utility>
using namespace std;


int main(){
	int n,m;
	cin >> n >> m;
	
	vector<pair<int,int> > arm(m);
	for(int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		arm[i]=make_pair(y,x);
	}
	sort(arm.begin(), arm.end());
	
	vector<int> lb(n+1, 1e9);
	vector<bool> used(m, false);
	for(int i=1; i<=n; i++){
		int lane=i;
		int position=0;
		while(1){
			vector<pair<int,int> >::iterator it;
			it = lower_bound(arm.begin(), arm.end(), make_pair(lane, position));
			if(it == arm.end() || it->first!=lane || used[it-arm.begin()]){
				lb[lane] = min(i, lb[lane]);
				break;
			}
			
			used[it-arm.begin()] = true;
			lb[lane] = min(i, lb[lane]);
			lane++;
			position = it->second;
		}
	}
	
	for(int i=0; i<m; i++){
		arm[i].first = -arm[i].first;
		used[i]=false;
	}
	sort(arm.begin(), arm.end());
	vector<int> ub(n+1, 0);
	for(int i=n; i>0; i--){
		int lane=i;
		int position=0;
		while(1){
			vector<pair<int,int> >::iterator it;
			it = lower_bound(arm.begin(), arm.end(), make_pair(-(lane-1), position));
			if(it == arm.end() || it->first!=-(lane-1)|| used[it-arm.begin()]){
				ub[lane] = max(i, ub[lane]);
				break;
			}
			
			used[it-arm.begin()] = true;
			ub[lane] = max(i, ub[lane]);
			lane--;
			position = it->second;
		}
	}
	
	for(int i=1; i<n; i++){
		cout << ub[i]-lb[i]+1 << " ";
	}
	cout << ub[n]-lb[n]+1 << endl;
	
	return 0;
}
```