#include<bits/stdc++.h>
using namespace std;
const int N = 200010;

int n, m;
pair<int, int> a[N];
int d[N][2];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++) scanf("%d%d",&a[i].first,&a[i].second);
	sort(a+1, a+1+m);
	for(int i = 1; i <= n; i++) d[i][0] = d[i][1] = 1;
	for(int i = 1; i <= m; i++)
	{
		int x = a[i].second;
		d[x][0] = max(d[x][0], d[x+1][0]+1);
		d[x+1][1] = max(d[x+1][1], d[x][1]+1);
	}
	for(int i = 1; i <= n; i++)
	{
		printf("%d",d[i][0]+d[i][1]-1);
		if(i != n) printf(" ");
	}
	printf("\n");
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;

int n, m;
pair<int, int> a[N];
int d[N][2];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++) scanf("%d%d",&a[i].first,&a[i].second);
	sort(a+1, a+1+m);
	for(int i = 1; i <= n; i++) d[i][0] = d[i][1] = 1;
	for(int i = 1; i <= m; i++)
	{
		int x = a[i].second;
		d[x][0] = max(d[x][0], d[x+1][0]+1);
		d[x+1][1] = max(d[x+1][1], d[x][1]+1);
	}
	for(int i = 1; i <= n; i++)
	{
		printf("%d",d[i][0]+d[i][1]-1);
		if(i != n) printf(" ");
	}
	printf("\n");
	return 0;
}
```