#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

struct ft{
	int N;
	vector<int> tree;
	inline void init(int n){
		tree.assign(n+3, 10234567);
		N = n;
	}
	inline void update(int i, int x){
		if(i == 0) return;
		for(;i <= N;i += i&(-i)) tree[i] = min(tree[i], x);
	}
	inline int query(int i){
		int res = 12034567;
		for(;i;i -= i&(-i)) res = min(res, tree[i]);
		return res;
	}
};
const int N = 1<<16;
vector<int> dis[2*N];
ft tree[2*N];

inline void addrange(int l, int r){
	for(l += N;l > 0;l >>= 1) dis[l].push_back(r);
}

inline void getready(){
	for(int u = 1;u < 2*N;u++){
		sort(all(dis[u]));
		dis[u].erase(unique(all(dis[u])), dis[u].end());
		tree[u].init(sz(dis[u]));
	}
}

inline void update(int l, int r, int id){
	for(l += N;l > 0;l >>= 1){
		int pos = upper_bound(all(dis[l]), r) - dis[l].begin();
		tree[l].update(pos, id);
	}
}

inline int get(int u, int r){
	int pos = upper_bound(all(dis[u]), r) - dis[u].begin();
	return tree[u].query(pos);
}

inline int query(int l, int r){
	int R = r; int res = 10234567;
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res = min(res, get(l++, R));
		if(r&1) res = min(res, get(--r, R));
	}
	return res;
}


vector<int> stuff[50005];
ii ranges[100005];

int dnc(int s, int e){
	int res = query(s,e);
	if(res > 110000) return 0;
	
	int a = ranges[res].first, b = ranges[res].second;
	return b-a+1 + dnc(s,a-1) + dnc(b+1,e);
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int l, r; cin >> l >> r;
		stuff[r-l+1].push_back(i);
		ranges[i] = ii(l,r);
		addrange(l,r);
	}
	
	getready();
	
	vector<int> ans;
	for(int x = n;x >= 1;x--){
		for(int i : stuff[x]) update(ranges[i].first, ranges[i].second, i);
		ans.push_back(dnc(1,n));
	}
	
	while(not ans.empty()){
		cout << ans.back() << '\n';
		ans.pop_back();
	}
}
