#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef pair<int,int> pii;

int main(){
  int n,m;
  cin >> n >> m;

  vector<pii> a(m);
  rep(i,m){
    cin >> a[i].first >> a[i].second;
  }
  sort(a.begin(), a.end());

  vector<int> l(n,0), r(n,0);
  rep(i,m){
    int y = a[i].second - 1;
    l[y+1] = l[y] + 1;
    r[y] = r[y+1] + 1;
  }

  rep(i,n){
    cout << r[i] + l[i] + 1 << " \n"[i==n-1];
  }
}
  
### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef pair<int,int> pii;

int main(){
  int n,m;
  cin >> n >> m;

  vector<pii> a(m);
  rep(i,m){
    cin >> a[i].first >> a[i].second;
  }
  sort(a.begin(), a.end());

  vector<int> l(n,0), r(n,0);
  rep(i,m){
    int y = a[i].second - 1;
    l[y+1] = l[y] + 1;
    r[y] = r[y+1] + 1;
  }

  rep(i,n){
    cout << r[i] + l[i] + 1 << " \n"[i==n-1];
  }
}
  
```