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

int main(){

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

  vector<pair<int, int>> xy(m);
  int x, y;
  for(int i = 0; i < m; i++){
    cin >> x >> y;

    xy[i] = make_pair(x, y - 1);
  }

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

  vector<int> sumLane(n, 1);
  vector<int> sumShare(n - 1, 0);

  for(int i = 0; i < m; i++){
    int temp = xy[i].second;

    int upper = sumLane[temp];
    int lower = sumLane[temp + 1];

    int share = sumShare[temp];

    int newSum = share + (upper - share) + (lower - share);

    sumLane[temp] = newSum;
    sumLane[temp + 1] = newSum;
    sumShare[temp] = newSum;
  }

  for(int i = 0; i < n; i++){
    cout << sumLane[i];
    if(i == n - 1){
      cout << endl;
    }
    else{
      cout << " ";
    }
  }
  
  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;

int main(){

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

  vector<pair<int, int>> xy(m);
  int x, y;
  for(int i = 0; i < m; i++){
    cin >> x >> y;

    xy[i] = make_pair(x, y - 1);
  }

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

  vector<int> sumLane(n, 1);
  vector<int> sumShare(n - 1, 0);

  for(int i = 0; i < m; i++){
    int temp = xy[i].second;

    int upper = sumLane[temp];
    int lower = sumLane[temp + 1];

    int share = sumShare[temp];

    int newSum = share + (upper - share) + (lower - share);

    sumLane[temp] = newSum;
    sumLane[temp + 1] = newSum;
    sumShare[temp] = newSum;
  }

  for(int i = 0; i < n; i++){
    cout << sumLane[i];
    if(i == n - 1){
      cout << endl;
    }
    else{
      cout << " ";
    }
  }
  
  return 0;
}


```