#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  vector<pair<int,int> > r(m);
  REP(i,m){cin>>r[i].first>>r[i].second;r[i].second--;}
  sort(r.begin(),r.end());
  int range[200003][2];
  REP(i,n){
      range[i][0] = range[i][1] = i;
  }
  REP(i,m){
      int ind = r[i].second;
      range[ind][0] = min(range[ind][0],ind);
      range[ind][1] = max(range[ind][1],max(ind + 1,range[ind+1][1]));
      range[ind+1][0] = min(range[ind+1][0],min(ind,range[ind][0]));
      range[ind+1][1] = max(range[ind+1][1],ind + 1);
  }
  REP(i,n){
      if(i)cout << ' ';
      cout << range[i][1] - range[i][0] + 1;
  }
  cout << endl;
  return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  vector<pair<int,int> > r(m);
  REP(i,m){cin>>r[i].first>>r[i].second;r[i].second--;}
  sort(r.begin(),r.end());
  int range[200003][2];
  REP(i,n){
      range[i][0] = range[i][1] = i;
  }
  REP(i,m){
      int ind = r[i].second;
      range[ind][0] = min(range[ind][0],ind);
      range[ind][1] = max(range[ind][1],max(ind + 1,range[ind+1][1]));
      range[ind+1][0] = min(range[ind+1][0],min(ind,range[ind][0]));
      range[ind+1][1] = max(range[ind+1][1],ind + 1);
  }
  REP(i,n){
      if(i)cout << ' ';
      cout << range[i][1] - range[i][0] + 1;
  }
  cout << endl;
  return 0;
}
```