#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<P> pt(m);
  for(int i = 0; i < m; i++) cin >> pt[i].first >> pt[i].second;
  sort(pt.begin(), pt.end());
  int up[n], lw[n];
  for(int i = 0; i < n; i++) up[i] = lw[i] = i;
  for(int i = 0; i < m; i++) {
    P p = pt[i];
    up[p.second] = up[p.second - 1];
    lw[p.second - 1] = lw[p.second];
  }
  for(int i = 0; i < n; i++) cout << lw[i] -up[i] + 1 << (i==n-1 ? '\n':' ');

  return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<P> pt(m);
  for(int i = 0; i < m; i++) cin >> pt[i].first >> pt[i].second;
  sort(pt.begin(), pt.end());
  int up[n], lw[n];
  for(int i = 0; i < n; i++) up[i] = lw[i] = i;
  for(int i = 0; i < m; i++) {
    P p = pt[i];
    up[p.second] = up[p.second - 1];
    lw[p.second - 1] = lw[p.second];
  }
  for(int i = 0; i < n; i++) cout << lw[i] -up[i] + 1 << (i==n-1 ? '\n':' ');

  return 0;
}
```