#include <bits/stdc++.h>
using namespace std;

#define int long long
using P = pair<int, int>;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, m;
  cin >> n >> m;

  vector<P> xy(m);
  for ( int i = 0; i < m; i++ ) {
    cin >> xy[i].first >> xy[i].second;
    xy[i].second--;    
  }

  sort(xy.begin(), xy.end());  

  vector<int> cntl(n, 0), cntr(n, 0);
  for ( int i = 0; i < m; i++ ) {
    int j = xy[i].second;    
    cntl[j+1] = cntl[j]+1;
    cntr[j] = cntr[j+1]+1;    
  }

  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << cntl[i]+cntr[i]+1;    
  }

  cout << endl;
  
  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 <bits/stdc++.h>
using namespace std;

#define int long long
using P = pair<int, int>;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, m;
  cin >> n >> m;

  vector<P> xy(m);
  for ( int i = 0; i < m; i++ ) {
    cin >> xy[i].first >> xy[i].second;
    xy[i].second--;    
  }

  sort(xy.begin(), xy.end());  

  vector<int> cntl(n, 0), cntr(n, 0);
  for ( int i = 0; i < m; i++ ) {
    int j = xy[i].second;    
    cntl[j+1] = cntl[j]+1;
    cntr[j] = cntr[j+1]+1;    
  }

  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << cntl[i]+cntr[i]+1;    
  }

  cout << endl;
  
  return 0;
}


```