#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#include <limits>
#include <list>
#include <stack>
#include <tuple>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef vector<ll> VL;
typedef vector<VL> VVL;


int main() {
	ios::sync_with_stdio(false);
	int n, m;
	while (cin >> n >> m) {
		VP R(m);
		for (int i = 0; i < m; ++i) {
			cin >> R[i].first >> R[i].second;
			--R[i].second;
		}
		sort(R.begin(), R.end());
		VI up(n, 1), down(n, 1);
		for (int i = 0; i < m; ++i) {
			int lni = R[i].second;
			up[lni+1] = up[lni] + 1;
			down[lni] = down[lni+1] + 1;
		}
		for (int i = 0; i < n; ++i) {
			cout << up[i] + down[i] -1 << (i+1 < n ? ' ' : '\n');
		}
	}
}
### 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 <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#include <limits>
#include <list>
#include <stack>
#include <tuple>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef vector<ll> VL;
typedef vector<VL> VVL;


int main() {
	ios::sync_with_stdio(false);
	int n, m;
	while (cin >> n >> m) {
		VP R(m);
		for (int i = 0; i < m; ++i) {
			cin >> R[i].first >> R[i].second;
			--R[i].second;
		}
		sort(R.begin(), R.end());
		VI up(n, 1), down(n, 1);
		for (int i = 0; i < m; ++i) {
			int lni = R[i].second;
			up[lni+1] = up[lni] + 1;
			down[lni] = down[lni+1] + 1;
		}
		for (int i = 0; i < n; ++i) {
			cout << up[i] + down[i] -1 << (i+1 < n ? ' ' : '\n');
		}
	}
}
```