#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

enum DIST{
	LEFT,
	RIGHT,
};

struct Info{
	Info(int arg_x,int arg_line_num){
		x = arg_x;
		line_num = arg_line_num;
	}
	bool operator<(const struct Info &arg) const{
			return x > arg.x;
	};
	int x,line_num;
};

int main(){

	int n,m,tmp_x,tmp_line_num;

	scanf("%d %d",&n,&m);

	int** dp = new int*[n+1];
	for(int i = 1; i <= n; i++){
		dp[i] = new int[2];
		dp[i][LEFT] = 0;
		dp[i][RIGHT] = 0;
	}

	priority_queue<Info> Q;

	for(int i = 0; i < m; i++){
		scanf("%d %d",&tmp_x,&tmp_line_num);
		Q.push(Info(tmp_x,tmp_line_num));
	}

	while(!Q.empty()){
		dp[Q.top().line_num+1][RIGHT] = max(dp[Q.top().line_num+1][RIGHT],dp[Q.top().line_num][RIGHT]+1);
		dp[Q.top().line_num][LEFT] = max(dp[Q.top().line_num][LEFT],dp[Q.top().line_num+1][LEFT]+1);
		Q.pop();
	}

	printf("%d",dp[1][LEFT]+dp[1][RIGHT]+1);
	for(int i = 2; i <= n; i++){
		printf(" %d",dp[i][LEFT]+dp[i][RIGHT]+1);
	}
	printf("\n");

	return 0;
}
### Prompt

In CPP, your task is to solve the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

enum DIST{
	LEFT,
	RIGHT,
};

struct Info{
	Info(int arg_x,int arg_line_num){
		x = arg_x;
		line_num = arg_line_num;
	}
	bool operator<(const struct Info &arg) const{
			return x > arg.x;
	};
	int x,line_num;
};

int main(){

	int n,m,tmp_x,tmp_line_num;

	scanf("%d %d",&n,&m);

	int** dp = new int*[n+1];
	for(int i = 1; i <= n; i++){
		dp[i] = new int[2];
		dp[i][LEFT] = 0;
		dp[i][RIGHT] = 0;
	}

	priority_queue<Info> Q;

	for(int i = 0; i < m; i++){
		scanf("%d %d",&tmp_x,&tmp_line_num);
		Q.push(Info(tmp_x,tmp_line_num));
	}

	while(!Q.empty()){
		dp[Q.top().line_num+1][RIGHT] = max(dp[Q.top().line_num+1][RIGHT],dp[Q.top().line_num][RIGHT]+1);
		dp[Q.top().line_num][LEFT] = max(dp[Q.top().line_num][LEFT],dp[Q.top().line_num+1][LEFT]+1);
		Q.pop();
	}

	printf("%d",dp[1][LEFT]+dp[1][RIGHT]+1);
	for(int i = 2; i <= n; i++){
		printf(" %d",dp[i][LEFT]+dp[i][RIGHT]+1);
	}
	printf("\n");

	return 0;
}
```