// Problem: P11368 [Ynoi2024] After god
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11368
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
	const int maxn = 1 << 20;
	
    char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = (1 << 20) + 50;

int n, m;
ll ans[maxn];
vector<pii> vc[maxn];

struct node {
	ll mn, smn, cnt;
	node(ll a = 0, ll b = 0, ll c = 0) : mn(a), smn(b), cnt(c) {}
};

inline node operator + (const node &a, const node &b) {
	node res;
	res.mn = min(a.mn, b.mn);
	res.smn = min(a.smn, b.smn);
	if (a.mn < b.mn) {
		res.smn = min(res.smn, b.mn);
	}
	if (a.mn > b.mn) {
		res.smn = min(res.smn, a.mn);
	}
	res.cnt = (a.mn == res.mn ? a.cnt : 0) + (b.mn == res.mn ? b.cnt : 0);
	return res;
}

struct vec {
	ll a0, a1, a2;
	vec(ll a = 0, ll b = 0, ll c = 0) : a0(a), a1(b), a2(c) {}
};

struct mat {
	ll a00, a01, a02, a10, a11, a12, a20, a21, a22;
	mat(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0, ll h = 0, ll i = 0) : a00(a), a01(b), a02(c), a10(d), a11(e), a12(f), a20(g), a21(h), a22(i) {}
} I;

inline bool operator == (const mat &a, const mat &b) {
	return a.a00 == b.a00 && a.a01 == b.a01 && a.a02 == b.a02 && a.a10 == b.a10 && a.a11 == b.a11 && a.a12 == b.a12 && a.a20 == b.a20 && a.a21 == b.a21 && a.a22 == b.a22;
}

inline bool operator != (const mat &a, const mat &b) {
	return a.a00 != b.a00 || a.a01 != b.a01 || a.a02 != b.a02 || a.a10 != b.a10 || a.a11 != b.a11 || a.a12 != b.a12 || a.a20 != b.a20 || a.a21 != b.a21 || a.a22 != b.a22;
}

inline vec operator + (const vec &a, const vec &b) {
	return vec(a.a0 + b.a0, a.a1 + b.a1, a.a2 + b.a2);
}

inline vec operator * (const vec &a, const mat &b) {
	vec res;
	res.a0 = a.a0 * b.a00 + a.a1 * b.a10 + a.a2 * b.a20;
	res.a1 = a.a0 * b.a01 + a.a1 * b.a11 + a.a2 * b.a21;
	res.a2 = a.a0 * b.a02 + a.a1 * b.a12 + a.a2 * b.a22;
	return res;
}
 
inline mat operator * (const mat &a, const mat &b) {
	mat res;
	res.a00 = a.a00 * b.a00 + a.a01 * b.a10 + a.a02 * b.a20;
	res.a01 = a.a00 * b.a01 + a.a01 * b.a11 + a.a02 * b.a21;
	res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22;
	res.a10 = a.a10 * b.a00 + a.a11 * b.a10 + a.a12 * b.a20;
	res.a11 = a.a10 * b.a01 + a.a11 * b.a11 + a.a12 * b.a21;
	res.a12 = a.a10 * b.a02 + a.a11 * b.a12 + a.a12 * b.a22;
	res.a20 = a.a20 * b.a00 + a.a21 * b.a10 + a.a22 * b.a20;
	res.a21 = a.a20 * b.a01 + a.a21 * b.a11 + a.a22 * b.a21;
	res.a22 = a.a20 * b.a02 + a.a21 * b.a12 + a.a22 * b.a22;
	return res;
}

namespace SGT {
	node a[maxn << 1];
	vec b[maxn << 1];
	ll cov[maxn << 1];
	mat tag[maxn << 1], tmn[maxn << 1];
	
	inline void pushup(int x) {
		a[x] = a[x << 1] + a[x << 1 | 1];
		b[x] = b[x << 1] + b[x << 1 | 1];
		b[x].a2 = a[x].cnt;
	}
	
	inline void pushtmn(int x, mat y) {
		tmn[x] = tmn[x] * y;
		b[x] = b[x] * y;
	}
	
	inline void pushtag(int x, mat y) {
		tag[x] = tag[x] * y;
		tmn[x] = tmn[x] * y;
		b[x] = b[x] * y;
	}
	
	inline void pushcov(int x, ll y) {
		if (y <= a[x].mn) {
			return;
		}
		a[x].mn = cov[x] = y;
	}
	
	inline void pushdown(int x) {
		if (cov[x] != -1) {
			pushcov(x << 1, cov[x]);
			pushcov(x << 1 | 1, cov[x]);
			cov[x] = -1;
		}
		if (tag[x] != I || tmn[x] != I) {
			if (a[x << 1].mn == a[x].mn) {
				pushtag(x << 1, tmn[x]);
			} else {
				pushtag(x << 1, tag[x]);
			}
			if (a[x << 1 | 1].mn == a[x].mn) {
				pushtag(x << 1 | 1, tmn[x]);
			} else {
				pushtag(x << 1 | 1, tag[x]);
			}
			tag[x] = tmn[x] = I;
		}
	}
	
	void build(int rt, int l, int r) {
		cov[rt] = -1;
		tag[rt] = tmn[rt] = I;
		if (l == r) {
			a[rt] = node(0, 1e18, 1);
			b[rt] = vec(0, 0, 1);
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, ll x) {
		if (x <= a[rt].mn) {
			return;
		}
		if (ql <= l && r <= qr && x < a[rt].smn) {
			pushtmn(rt, mat(1, 0, 0, 0, 1, 0, 0, x - a[rt].mn, 1));
			pushcov(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	ll query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return b[rt].a0 + b[rt].a1;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		ll res = 0;
		if (ql <= mid) {
			res += query(rt << 1, l, mid, ql, qr);
		}
		if (qr > mid) {
			res += query(rt << 1 | 1, mid + 1, r, ql, qr);
		}
		return res;
	}
}

void solve() {
	I.a00 = I.a11 = I.a22 = 1;
	n = read();
	m = read();
	for (int i = 1, x, y; i <= m; ++i) {
		x = read();
		y = read();
		vc[x].pb(i, y);
	}
	SGT::build(1, 1, m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < (int)vc[i].size(); ++j) {
			SGT::update(1, 1, m, vc[i][j].fst, j == (int)vc[i].size() - 1 ? m : vc[i][j + 1].fst - 1, vc[i][j].scd);
			ans[vc[i][j].fst] = SGT::query(1, 1, m, 1, vc[i][j].fst);
		}
		SGT::pushtag(1, mat(1, 0, 0, 1, 1, 0, 0, 0, 1));
	}
	for (int i = 1; i <= m; ++i) {
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}