#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  std::vector<std::pair<int,int>> robot;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    robot.push_back(std::make_pair(x,y));
  }
  std::sort(robot.begin(), robot.end());

  std::vector<int> min(n+1),max(n+1);
  for(int i=1;i<=n;i++){
    min[i]=i;
    max[i]=i;
  }

  for(auto r:robot){
    int u=r.second;
    int l=r.second+1;
    min[u]=std::min(min[u],min[l]);
    max[u]=std::max(max[u],max[l]);
    min[l]=min[u];
    max[l]=max[u];
  }

  for(int i=1;i<n;i++){
    cout<<max[i]-min[i]+1<<" ";
  }
  cout<<max[n]-min[n]+1<<endl;



  return 0;
}

### 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 <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  std::vector<std::pair<int,int>> robot;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    robot.push_back(std::make_pair(x,y));
  }
  std::sort(robot.begin(), robot.end());

  std::vector<int> min(n+1),max(n+1);
  for(int i=1;i<=n;i++){
    min[i]=i;
    max[i]=i;
  }

  for(auto r:robot){
    int u=r.second;
    int l=r.second+1;
    min[u]=std::min(min[u],min[l]);
    max[u]=std::max(max[u],max[l]);
    min[l]=min[u];
    max[l]=max[u];
  }

  for(int i=1;i<n;i++){
    cout<<max[i]-min[i]+1<<" ";
  }
  cout<<max[n]-min[n]+1<<endl;



  return 0;
}

```