#include <iostream>
#include <vector>
#include <algorithm>
int dp[200001][2] = { 0 };

int main() {
	int n, m;
	std::vector<std::pair<int, int>> robot;

	std::cin >> n >> m;
	robot.reserve(m);
	for (int i = 0; i < m; i++) {
		int x, y; std::cin >> x >> y;
		robot.push_back(std::make_pair(x, y));
	}
	std::sort(robot.begin(), robot.end());

	for (auto& x : robot) {
		dp[x.second][1] = dp[x.second + 1][1] + 1;
		dp[x.second + 1][0] = dp[x.second][0] + 1;
	}

	for (int i = 1; i <= n; i++) {
		std::cout << dp[i][0] + dp[i][1] + 1;
		if (i != n) std::cout << " ";
	}
	std::cout << std::endl;
	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 <iostream>
#include <vector>
#include <algorithm>
int dp[200001][2] = { 0 };

int main() {
	int n, m;
	std::vector<std::pair<int, int>> robot;

	std::cin >> n >> m;
	robot.reserve(m);
	for (int i = 0; i < m; i++) {
		int x, y; std::cin >> x >> y;
		robot.push_back(std::make_pair(x, y));
	}
	std::sort(robot.begin(), robot.end());

	for (auto& x : robot) {
		dp[x.second][1] = dp[x.second + 1][1] + 1;
		dp[x.second + 1][0] = dp[x.second][0] + 1;
	}

	for (int i = 1; i <= n; i++) {
		std::cout << dp[i][0] + dp[i][1] + 1;
		if (i != n) std::cout << " ";
	}
	std::cout << std::endl;
	return 0;
}

```