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

int main(){
  int N, M, i;
  scanf("%d%d", &N, &M);
  vector<pair<int, int>> xy(M);
  for(i = 0; i < M; i++){
    scanf("%d%d", &xy[i].first, &xy[i].second);
    xy[i].second--;
  }
  sort(xy.begin(), xy.end());
  vector<vector<int>> used(N - 1, vector<int>(0)), up(N - 1, vector<int>(0)), down(N - 1, vector<int>(0));
  for(i = 0; i < M; i++){
//    printf("i = %d\n", i);
    int j = xy[i].second;
//    printf("j = %d\n", j);
    if(j == 0){
      up[j].push_back(0);
    }
    else if(used[j - 1].size() == 0){
      up[j].push_back(j);
    }
    else{
      up[j].push_back(up[j - 1][used[j - 1].size() - 1]);
    }
    if(j + 1 == N - 1){
      down[j].push_back(N - 1);
    }
    else if(used[j + 1].size() == 0){
      down[j].push_back(j + 1);
    }
    else{
      down[j].push_back(down[j + 1][used[j + 1].size() - 1]);
    }
    used[j].push_back(xy[i].first);
  }
//  printf("output\n");
  for(i = 0; i < N; i++){
//    printf("i = %d\n", i);
    int l, r;
    if(i == 0){
      l = 0;
    }
    else if(used[i - 1].size() == 0){
      l = i;
    }
    else{
      l = up[i - 1][used[i - 1].size() - 1];
    }
//    printf("l = %d\n", l);
    if(i == N - 1){
      r = N - 1;
    }
    else if(used[i].size() == 0){
      r = i;
    }
    else{
//      printf("test5\n");
      r = down[i][used[i].size() - 1];
    }
//    printf("r = %d\n", r);
    printf("%d", r - l + 1);
    if(i < N - 1){
      printf(" ");
    }
    else{
      printf("\n");
    }
  }
  return 0;
}


### Prompt

Your challenge is to write a cpp solution to 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, i;
  scanf("%d%d", &N, &M);
  vector<pair<int, int>> xy(M);
  for(i = 0; i < M; i++){
    scanf("%d%d", &xy[i].first, &xy[i].second);
    xy[i].second--;
  }
  sort(xy.begin(), xy.end());
  vector<vector<int>> used(N - 1, vector<int>(0)), up(N - 1, vector<int>(0)), down(N - 1, vector<int>(0));
  for(i = 0; i < M; i++){
//    printf("i = %d\n", i);
    int j = xy[i].second;
//    printf("j = %d\n", j);
    if(j == 0){
      up[j].push_back(0);
    }
    else if(used[j - 1].size() == 0){
      up[j].push_back(j);
    }
    else{
      up[j].push_back(up[j - 1][used[j - 1].size() - 1]);
    }
    if(j + 1 == N - 1){
      down[j].push_back(N - 1);
    }
    else if(used[j + 1].size() == 0){
      down[j].push_back(j + 1);
    }
    else{
      down[j].push_back(down[j + 1][used[j + 1].size() - 1]);
    }
    used[j].push_back(xy[i].first);
  }
//  printf("output\n");
  for(i = 0; i < N; i++){
//    printf("i = %d\n", i);
    int l, r;
    if(i == 0){
      l = 0;
    }
    else if(used[i - 1].size() == 0){
      l = i;
    }
    else{
      l = up[i - 1][used[i - 1].size() - 1];
    }
//    printf("l = %d\n", l);
    if(i == N - 1){
      r = N - 1;
    }
    else if(used[i].size() == 0){
      r = i;
    }
    else{
//      printf("test5\n");
      r = down[i][used[i].size() - 1];
    }
//    printf("r = %d\n", r);
    printf("%d", r - l + 1);
    if(i < N - 1){
      printf(" ");
    }
    else{
      printf("\n");
    }
  }
  return 0;
}


```