#include <iostream>
#include <algorithm>
using namespace std;

int N,M;
int L[200010],R[200010];
pair<int,int> A[100010];

int main(){
    cin >> N >> M;
    int x,y;
    for(int i=1;i<=M;i++){
        cin >> x >> y;
        A[i] = {x,y};
    }
    sort(A+1,A+M+1);
    for(int i=1;i<=N;i++) {L[i] = i; R[i] = i;}
    for(int i=1;i<=M;i++){
        int a = A[i].second;
        R[a] = R[a+1];
        L[a+1] = L[a];
    }
    for(int i=1;i<=N;i++) cout << R[i]-L[i]+1 << (i!=N? " ":"\n");
}

### 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 <algorithm>
using namespace std;

int N,M;
int L[200010],R[200010];
pair<int,int> A[100010];

int main(){
    cin >> N >> M;
    int x,y;
    for(int i=1;i<=M;i++){
        cin >> x >> y;
        A[i] = {x,y};
    }
    sort(A+1,A+M+1);
    for(int i=1;i<=N;i++) {L[i] = i; R[i] = i;}
    for(int i=1;i<=M;i++){
        int a = A[i].second;
        R[a] = R[a+1];
        L[a+1] = L[a];
    }
    for(int i=1;i<=N;i++) cout << R[i]-L[i]+1 << (i!=N? " ":"\n");
}

```