#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
vector<int>x[1000000], B[1000000]; int a[300000], b[300000], l[1000000], r[1000000], X[1000000], Y[1000000], n, m;
map<pair<int, int>, int>M;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
map<pair<int, int>, int>used;
vector<pair<int, int>>Vec;
void add_edge() {
	for (int i = 1; i <= n; i++)sort(B[i].begin(), B[i].end());
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < B[i].size(); j++) { Vec.push_back(make_pair(B[i][j], i)); }
	}
	sort(Vec.begin(), Vec.end()); for (int i = 0; i < Vec.size(); i++) { M[Vec[i]] = i + 1; X[i + 1] = Vec[i].first; Y[i + 1] = Vec[i].second; }
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < B[i].size() - 1; j++) {
			x[M[make_pair(B[i][j], i)]].push_back(M[make_pair(B[i][j + 1], i)]);
		}
	}
	for (int i = 0; i < m; i++) {
		x[M[make_pair(a[i] * 2, b[i])]].push_back(M[make_pair(a[i] * 2 + 1, b[i] + 1)]);
		x[M[make_pair(a[i] * 2, b[i] + 1)]].push_back(M[make_pair(a[i] * 2 + 1, b[i])]);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { B[i].push_back(0); B[i].push_back(500000); }
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		B[b[i]].push_back(a[i] * 2); B[b[i]].push_back(a[i] * 2 + 1);
		B[b[i] + 1].push_back(a[i] * 2); B[b[i] + 1].push_back(a[i] * 2 + 1);
	}
	add_edge();
	for (int i = 0; i < 1000000; i++) { l[i] = 1000000; r[i] = 0; }
	for (int i = 1; i <= n; i++) { Q.push(make_pair(0, M[make_pair(0, i)])); l[M[make_pair(0, i)]] = i; r[M[make_pair(0, i)]] = i; }
	while (!Q.empty()) {
		int a1 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a1].size(); i++) {
			if (X[a1] >= X[x[a1][i]] || used[make_pair(a1, x[a1][i])] == 1)continue;
			Q.push(make_pair(X[x[a1][i]], x[a1][i])); used[make_pair(a1, x[a1][i])] = 1;
			l[x[a1][i]] = min(l[x[a1][i]], min(l[a1], Y[x[a1][i]]));
			r[x[a1][i]] = max(r[x[a1][i]], max(r[a1], Y[x[a1][i]]));
		}
	}
	for (int i = 1; i <= n; i++) { 
		if (i >= 2)cout << ' '; 
		cout << r[M[make_pair(500000, i)]] - l[M[make_pair(500000, i)]] + 1;
	}
	cout << endl;
	return 0;
}
### Prompt

Create a solution in cpp for 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<map>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
vector<int>x[1000000], B[1000000]; int a[300000], b[300000], l[1000000], r[1000000], X[1000000], Y[1000000], n, m;
map<pair<int, int>, int>M;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
map<pair<int, int>, int>used;
vector<pair<int, int>>Vec;
void add_edge() {
	for (int i = 1; i <= n; i++)sort(B[i].begin(), B[i].end());
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < B[i].size(); j++) { Vec.push_back(make_pair(B[i][j], i)); }
	}
	sort(Vec.begin(), Vec.end()); for (int i = 0; i < Vec.size(); i++) { M[Vec[i]] = i + 1; X[i + 1] = Vec[i].first; Y[i + 1] = Vec[i].second; }
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < B[i].size() - 1; j++) {
			x[M[make_pair(B[i][j], i)]].push_back(M[make_pair(B[i][j + 1], i)]);
		}
	}
	for (int i = 0; i < m; i++) {
		x[M[make_pair(a[i] * 2, b[i])]].push_back(M[make_pair(a[i] * 2 + 1, b[i] + 1)]);
		x[M[make_pair(a[i] * 2, b[i] + 1)]].push_back(M[make_pair(a[i] * 2 + 1, b[i])]);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { B[i].push_back(0); B[i].push_back(500000); }
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		B[b[i]].push_back(a[i] * 2); B[b[i]].push_back(a[i] * 2 + 1);
		B[b[i] + 1].push_back(a[i] * 2); B[b[i] + 1].push_back(a[i] * 2 + 1);
	}
	add_edge();
	for (int i = 0; i < 1000000; i++) { l[i] = 1000000; r[i] = 0; }
	for (int i = 1; i <= n; i++) { Q.push(make_pair(0, M[make_pair(0, i)])); l[M[make_pair(0, i)]] = i; r[M[make_pair(0, i)]] = i; }
	while (!Q.empty()) {
		int a1 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a1].size(); i++) {
			if (X[a1] >= X[x[a1][i]] || used[make_pair(a1, x[a1][i])] == 1)continue;
			Q.push(make_pair(X[x[a1][i]], x[a1][i])); used[make_pair(a1, x[a1][i])] = 1;
			l[x[a1][i]] = min(l[x[a1][i]], min(l[a1], Y[x[a1][i]]));
			r[x[a1][i]] = max(r[x[a1][i]], max(r[a1], Y[x[a1][i]]));
		}
	}
	for (int i = 1; i <= n; i++) { 
		if (i >= 2)cout << ' '; 
		cout << r[M[make_pair(500000, i)]] - l[M[make_pair(500000, i)]] + 1;
	}
	cout << endl;
	return 0;
}
```