#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main(){
  int n, m, x, y;
  cin >> n >> m;
  vector< pair<int,int> > V;
  for(int i = 0; i < m; ++i){
    cin >> x >> y;
    V.push_back(make_pair(x,y));
  }
  sort(V.begin(),V.end());
  int D[2][n], ans[n], C[n];
  for(int i = 0; i < 2; ++i)
    fill(D[i],D[i]+n,1);
  fill(ans,ans+n,1);
  fill(C,C+n,-1);
  for(int i = 0; i < m; ++i){
    x = V[i].first;
    y = V[i].second;
    ans[y-1] += D[0][y];
    ans[y] += D[1][y-1];
    D[0][y-1] += D[0][y];
    D[1][y] += D[1][y-1];
    D[1][y-1] = 0;
    D[0][y] = 0;
  }
  for(int i = 0; i < n-1; ++i)
    cout << ans[i] << " ";
  cout << ans[n-1] << endl;

  return 0;
}
### Prompt

Generate 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 <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main(){
  int n, m, x, y;
  cin >> n >> m;
  vector< pair<int,int> > V;
  for(int i = 0; i < m; ++i){
    cin >> x >> y;
    V.push_back(make_pair(x,y));
  }
  sort(V.begin(),V.end());
  int D[2][n], ans[n], C[n];
  for(int i = 0; i < 2; ++i)
    fill(D[i],D[i]+n,1);
  fill(ans,ans+n,1);
  fill(C,C+n,-1);
  for(int i = 0; i < m; ++i){
    x = V[i].first;
    y = V[i].second;
    ans[y-1] += D[0][y];
    ans[y] += D[1][y-1];
    D[0][y-1] += D[0][y];
    D[1][y] += D[1][y-1];
    D[1][y-1] = 0;
    D[0][y] = 0;
  }
  for(int i = 0; i < n-1; ++i)
    cout << ans[i] << " ";
  cout << ans[n-1] << endl;

  return 0;
}
```