#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main(void) {
	int n, m;
	cin>>n>>m;
	vector<P> arm(m);
	REP(i, m) {
		cin>>arm[i].first>>arm[i].second;
		--arm[i].second;
	}
	sort(ALL(arm));
	vector<P> rng(n);
	REP(i, n) {
		rng[i].first = i;
		rng[i].second = i;
	}
	REP(i, m) {
		rng[arm[i].second].second = max(rng[arm[i].second].second, rng[arm[i].second + 1].second);
		rng[arm[i].second + 1].first = min(rng[arm[i].second + 1].first, rng[arm[i].second].first);
	}
	REP(i, n) {
		cout<<rng[i].second - rng[i].first + 1;
		if(i != n - 1) cout<<' ';
		else cout<<endl;
	}
}
### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main(void) {
	int n, m;
	cin>>n>>m;
	vector<P> arm(m);
	REP(i, m) {
		cin>>arm[i].first>>arm[i].second;
		--arm[i].second;
	}
	sort(ALL(arm));
	vector<P> rng(n);
	REP(i, n) {
		rng[i].first = i;
		rng[i].second = i;
	}
	REP(i, m) {
		rng[arm[i].second].second = max(rng[arm[i].second].second, rng[arm[i].second + 1].second);
		rng[arm[i].second + 1].first = min(rng[arm[i].second + 1].first, rng[arm[i].second].first);
	}
	REP(i, n) {
		cout<<rng[i].second - rng[i].first + 1;
		if(i != n - 1) cout<<' ';
		else cout<<endl;
	}
}
```