#include <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200005;

int n, m;
int lt[N];
int rt[N];

struct transfer
{
	int x, y;

	friend bool operator < (const transfer &a, const transfer &b)
	{
		return a.x < b.x;
	}
}tran[N];

signed main(void)
{
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
		cin >> tran[i].x >> tran[i].y;
	sort(tran + 1, tran + 1 + m);
	for (int i = 1; i <= n; ++i)
		lt[i] = rt[i] = 1;
	for (int i = 1; i <= m; ++i)
	{
		int a = tran[i].y, b = a + 1;
		lt[a] = lt[b] + 1;
		rt[b] = rt[a] + 1;
	}
	for (int i = 1; i < n; ++i)
		cout << lt[i] + rt[i] - 1 << " ";
	cout << lt[n] + rt[n] - 1 << endl;	//system("pause");
}
### Prompt

Your challenge is to write 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 <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200005;

int n, m;
int lt[N];
int rt[N];

struct transfer
{
	int x, y;

	friend bool operator < (const transfer &a, const transfer &b)
	{
		return a.x < b.x;
	}
}tran[N];

signed main(void)
{
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
		cin >> tran[i].x >> tran[i].y;
	sort(tran + 1, tran + 1 + m);
	for (int i = 1; i <= n; ++i)
		lt[i] = rt[i] = 1;
	for (int i = 1; i <= m; ++i)
	{
		int a = tran[i].y, b = a + 1;
		lt[a] = lt[b] + 1;
		rt[b] = rt[a] + 1;
	}
	for (int i = 1; i < n; ++i)
		cout << lt[i] + rt[i] - 1 << " ";
	cout << lt[n] + rt[n] - 1 << endl;	//system("pause");
}
```