#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i=s;i<e;i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(),(a).end()
typedef long long LL;
const LL mod = 1000000007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int> > p(m);
    REP(i, m){
       cin >> p[i].first >> p[i].second;
       p[i].second--;
    }
    sort(all(p));
    vector<int> L(n), R(n);
    REP(i, n){
        L[i] = i;
        R[i] = i;
    }
    REP(i, m){
        int y = p[i].second;
        L[y] = min(L[y], L[y+1]);
        L[y+1] = min(L[y], L[y+1]);
        R[y] = max(R[y], R[y+1]);
        R[y+1] = max(R[y], R[y+1]);
    }
    REP(i, n){
        cout << R[i]-L[i]+1 << (i==n-1 ? "\n":" ");
    }
}


### Prompt

Please provide a CPP coded solution to the problem described below:

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 FOR(i,s,e) for(int i=s;i<e;i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(),(a).end()
typedef long long LL;
const LL mod = 1000000007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int> > p(m);
    REP(i, m){
       cin >> p[i].first >> p[i].second;
       p[i].second--;
    }
    sort(all(p));
    vector<int> L(n), R(n);
    REP(i, n){
        L[i] = i;
        R[i] = i;
    }
    REP(i, m){
        int y = p[i].second;
        L[y] = min(L[y], L[y+1]);
        L[y+1] = min(L[y], L[y+1]);
        R[y] = max(R[y], R[y+1]);
        R[y+1] = max(R[y], R[y+1]);
    }
    REP(i, n){
        cout << R[i]-L[i]+1 << (i==n-1 ? "\n":" ");
    }
}


```