#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <stack>
typedef long long ll;
#define INF 0x3f3f3f3f

using namespace std;
struct Node {
	int x, y;

};
bool cmp(Node n1, Node n2) {
	return n1.x < n2.x;
}

ll dp[200000 + 10];
Node node[100000 + 10];
ll pre[200000 + 10][2];
void solve() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
			dp[i] = dp[i] = 1;
	}
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &node[i].x, &node[i].y);
	}
	
	sort(node, node + m, cmp);
	
	for(int i = 0; i < m; i++) {
		ll pre1 = dp[node[i].y], pre2 = dp[node[i].y + 1];
		dp[node[i].y] += pre2 - pre[node[i].y][1];
		dp[node[i].y + 1] += pre1 - pre[node[i].y + 1][0];
		
		pre[node[i].y][1] = dp[node[i].y];
		pre[node[i].y + 1][0] = dp[node[i].y + 1];
		
	}
	
	printf("%lld", dp[1]);
	for(int i = 2; i <= n; i++) {
		printf(" %lld", dp[i]);
	}
	printf("\n");
		
}
int main(int argc, char *argv[]) {
	solve();
}
### 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 <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <stack>
typedef long long ll;
#define INF 0x3f3f3f3f

using namespace std;
struct Node {
	int x, y;

};
bool cmp(Node n1, Node n2) {
	return n1.x < n2.x;
}

ll dp[200000 + 10];
Node node[100000 + 10];
ll pre[200000 + 10][2];
void solve() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
			dp[i] = dp[i] = 1;
	}
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &node[i].x, &node[i].y);
	}
	
	sort(node, node + m, cmp);
	
	for(int i = 0; i < m; i++) {
		ll pre1 = dp[node[i].y], pre2 = dp[node[i].y + 1];
		dp[node[i].y] += pre2 - pre[node[i].y][1];
		dp[node[i].y + 1] += pre1 - pre[node[i].y + 1][0];
		
		pre[node[i].y][1] = dp[node[i].y];
		pre[node[i].y + 1][0] = dp[node[i].y + 1];
		
	}
	
	printf("%lld", dp[1]);
	for(int i = 2; i <= n; i++) {
		printf(" %lld", dp[i]);
	}
	printf("\n");
		
}
int main(int argc, char *argv[]) {
	solve();
}
```