#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;

int main() {
  int n,m;
  cin >> n >> m;
  P a[m];
  for(int i=0; i<m; i++) cin >> a[i].F >> a[i].S;
  sort(a,a+m);
  P dp[n];
  for(int i=0; i<n; i++) dp[i]=P(i,i);
  for(int i=0; i<m; i++) {
    dp[a[i].S-1].F=min(dp[a[i].S-1].F,dp[a[i].S].F);
    dp[a[i].S-1].S=max(dp[a[i].S-1].S,dp[a[i].S].S);
    dp[a[i].S].F=min(dp[a[i].S].F,dp[a[i].S-1].F);
    dp[a[i].S].S=max(dp[a[i].S].S,dp[a[i].S-1].S);
  }
  for(int i=0; i<n; i++) {
    if(i) cout << " ";
    cout << dp[i].S-dp[i].F+1;
  }
  cout << 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 <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;

int main() {
  int n,m;
  cin >> n >> m;
  P a[m];
  for(int i=0; i<m; i++) cin >> a[i].F >> a[i].S;
  sort(a,a+m);
  P dp[n];
  for(int i=0; i<n; i++) dp[i]=P(i,i);
  for(int i=0; i<m; i++) {
    dp[a[i].S-1].F=min(dp[a[i].S-1].F,dp[a[i].S].F);
    dp[a[i].S-1].S=max(dp[a[i].S-1].S,dp[a[i].S].S);
    dp[a[i].S].F=min(dp[a[i].S].F,dp[a[i].S-1].F);
    dp[a[i].S].S=max(dp[a[i].S].S,dp[a[i].S-1].S);
  }
  for(int i=0; i<n; i++) {
    if(i) cout << " ";
    cout << dp[i].S-dp[i].F+1;
  }
  cout << endl;
  return 0;
}
```