#include <iostream>
#include <algorithm>
using namespace std;

struct Pos {
	int y, x;
	Pos() {}
	Pos(int y, int x) { this->y = y; this->x = x; }
	bool operator<(const Pos &r) const { return (y != r.y) ? y < r.y : x < r.x; }
};

int n, m;
Pos arm[100000];
int dp[2][100000];

//?§??????????(dir=0:???, dir=1:???), (?????£????????£???)??¢???????????????id, ??????????????????????????´???(0-indexed)?????????
int dfs(int dir, int id) {
	int nextId;

	if (dp[dir][id] != -1) {
		return dp[dir][id];
	}
	
	if (dir == 0) {
		nextId = upper_bound(arm, arm + m, Pos(arm[id].y - 1, arm[id].x)) - 1 - arm;
		if (nextId < 0 || arm[nextId].y != arm[id].y - 1) return arm[id].y;
		return dp[dir][id] = dfs(dir, nextId);
	}
	
	nextId = upper_bound(arm, arm + m, Pos(arm[id].y + 1, arm[id].x)) - 1 - arm;
	if (nextId < 0 || arm[nextId].y != arm[id].y + 1) return arm[id].y + 1;
	return dp[dir][id] = dfs(dir, nextId);
}

int main() {
	int i, j;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) { cin >> arm[i].x >> arm[i].y; arm[i].y--; }
	sort(arm, arm + m);
	
	for (i = 0; i < 2; i++) for (j = 0; j < m; j++) dp[i][j] = -1;
	
	int id;
	for (i = 0; i < n; i++) {
		id = lower_bound(arm, arm + m, Pos(i, -1)) - 1 - arm;
		int low  = ((id < 0 || arm[id].y != i - 1) ? i : dfs(0, id));
		id = lower_bound(arm, arm + m, Pos(i + 1, -1)) - 1 - arm;
		int high = ((id < 0 || arm[id].y != i) ? i : dfs(1, id));
		cout << high - low + 1;
		if (i + 1 < n) cout << " ";
	}
	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 <algorithm>
using namespace std;

struct Pos {
	int y, x;
	Pos() {}
	Pos(int y, int x) { this->y = y; this->x = x; }
	bool operator<(const Pos &r) const { return (y != r.y) ? y < r.y : x < r.x; }
};

int n, m;
Pos arm[100000];
int dp[2][100000];

//?§??????????(dir=0:???, dir=1:???), (?????£????????£???)??¢???????????????id, ??????????????????????????´???(0-indexed)?????????
int dfs(int dir, int id) {
	int nextId;

	if (dp[dir][id] != -1) {
		return dp[dir][id];
	}
	
	if (dir == 0) {
		nextId = upper_bound(arm, arm + m, Pos(arm[id].y - 1, arm[id].x)) - 1 - arm;
		if (nextId < 0 || arm[nextId].y != arm[id].y - 1) return arm[id].y;
		return dp[dir][id] = dfs(dir, nextId);
	}
	
	nextId = upper_bound(arm, arm + m, Pos(arm[id].y + 1, arm[id].x)) - 1 - arm;
	if (nextId < 0 || arm[nextId].y != arm[id].y + 1) return arm[id].y + 1;
	return dp[dir][id] = dfs(dir, nextId);
}

int main() {
	int i, j;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) { cin >> arm[i].x >> arm[i].y; arm[i].y--; }
	sort(arm, arm + m);
	
	for (i = 0; i < 2; i++) for (j = 0; j < m; j++) dp[i][j] = -1;
	
	int id;
	for (i = 0; i < n; i++) {
		id = lower_bound(arm, arm + m, Pos(i, -1)) - 1 - arm;
		int low  = ((id < 0 || arm[id].y != i - 1) ? i : dfs(0, id));
		id = lower_bound(arm, arm + m, Pos(i + 1, -1)) - 1 - arm;
		int high = ((id < 0 || arm[id].y != i) ? i : dfs(1, id));
		cout << high - low + 1;
		if (i + 1 < n) cout << " ";
	}
	cout << endl;
	return 0;
}
```