

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>


int n, m;
std::pair<int, int> robot[110000];
int range[210000][4];

int main()
{
	using std::cin;
	std::cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> robot[i].first >> robot[i].second; --robot[i].second;
	}
	//for (int rrr = 0; rrr < m; ++rrr)
	//{
	//	auto& r = robot[rrr];
	//	std::cout << r.second << ";"  << std::endl;
	//}
	std::sort(robot, robot + m);

	for (int i = 0; i < n; i++)
	{
		range[i][0] = range[i][1] = i;
	}

	for (int rrr = 0; rrr < m; ++rrr)
	{
		auto& r = robot[rrr];
		range[r.second][0] = range[r.second + 1][0] = std::min(range[r.second][0], range[r.second + 1][0]);
		range[r.second][1] = range[r.second + 1][1] = std::max(range[r.second][1], range[r.second + 1][1]);

		//std::cout << r.second << ";" << range[r.second][0] << " " << range[r.second][1] << std::endl;
	}

	std::cout << (range[0][1] - range[0][0] + 1);
	for (int i = 1; i < n; i++) {
		std::cout << " " << (range[i][1] - range[i][0] + 1);
	}
	std::cout << std::endl;
}


#endif


### Prompt

Generate a Cpp solution to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp


#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>


int n, m;
std::pair<int, int> robot[110000];
int range[210000][4];

int main()
{
	using std::cin;
	std::cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> robot[i].first >> robot[i].second; --robot[i].second;
	}
	//for (int rrr = 0; rrr < m; ++rrr)
	//{
	//	auto& r = robot[rrr];
	//	std::cout << r.second << ";"  << std::endl;
	//}
	std::sort(robot, robot + m);

	for (int i = 0; i < n; i++)
	{
		range[i][0] = range[i][1] = i;
	}

	for (int rrr = 0; rrr < m; ++rrr)
	{
		auto& r = robot[rrr];
		range[r.second][0] = range[r.second + 1][0] = std::min(range[r.second][0], range[r.second + 1][0]);
		range[r.second][1] = range[r.second + 1][1] = std::max(range[r.second][1], range[r.second + 1][1]);

		//std::cout << r.second << ";" << range[r.second][0] << " " << range[r.second][1] << std::endl;
	}

	std::cout << (range[0][1] - range[0][0] + 1);
	for (int i = 1; i < n; i++) {
		std::cout << " " << (range[i][1] - range[i][0] + 1);
	}
	std::cout << std::endl;
}


#endif


```