#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 200010, maxm = maxn + (maxn << 1), inf = 1e8;
int n, m;
map< pair<int,int>, int > id;
pair<int,int> to_loc[ maxm ];
int dp[ maxm ], cnt, rb[maxn], res[maxn], lb[maxn];
bool vis[maxm];
struct sgt {
	int v[maxn<<1], sz;
	void init(int ns = n+1) {
		sz = ns;
		fill(v, v+sz+sz, inf);
	}
	void mo(int i, int val) {
		v[i] = min(v[i], val);
	}
	int query(int i) {
		int res = inf;
		for (i += sz;i;i>>=1)
			res = min(res, v[i]);
		return res;
	}
	void modify(int l, int r, int val) {
		l += sz, r += sz;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) mo(l++, val);
			if (r&1) mo(--r, val);
		}
	}
}tree;
//           [u, len]
vector<pair<int,int>> edge[maxm];
map<pair<int,int>, int> Findnxt;
int create(int x, int y) {
	if (id.count({x, y})) return id[{x, y}];
	assert(cnt < maxm);
	to_loc[ cnt ] = {x, y};
	return id[{x, y}] = cnt++;
}
vector<int> start;
void precal() {
	vector<pair<int,int>> loc;
	for (int i = n-1;i >= 0;--i)
		loc.pb(i, rb[i]+1);
	for (int i = 0;i < n;++i)
		loc.pb(0, i);
	tree.init(m);
	for (int i = n-1;i >= 0;--i) {
		tree.modify(lb[i], rb[i]+1, i);
		if (rb[i]+1 < m) 
			Findnxt[{i, rb[i]+1}] = tree.query(rb[i]+1);
	}
	for (int i = 0;i < m;++i) if (i < lb[0] || i > rb[0])
		Findnxt[{0, i}] = tree.query(i);
}
void build(int t) {
	int x = 0, y = t, h = 0, now = create(x, y);
	start.pb(now);
	//DE(t, '\n');
	while (x < n) {
		//DE(x, ' '), DE(y, '\n');
		// case one : go horizontal
		int nx, ny;
		if (y <= rb[x] && y >= lb[x])
			nx = x, ny = rb[x]+1;
		else nx = Findnxt[{x, y}], ny = y;
//		cerr << "X Y " << x << ' ' << y << '\n';
//		cerr << "NX NY " << nx << ' ' << ny << '\n';
		if (nx == inf) nx = n;

		if (nx == x) {
			if (rb[x] == m-1) {
				//cerr << "No chance\n";
				break;
			}
			int nxt = create(nx, rb[x]+1);
			edge[now].pb(nxt, rb[x]+1 - y);
			now = nxt, y = rb[x]+1;
			continue;
		}
		// case zero : go free
		
		if (nx == n) {
			edge[now].pb(create(nx, ny), 0);
			break;
		}
		// case two : meet already exist
		if (id.count({nx, ny})) {
			//cerr << "Existed\n";
			edge[now].pb(id[{nx, ny}], 0);
			break;
		}
		// case three : meet not exist
		int nxt = create(nx, ny);
		edge[now].pb(nxt, 0);
		now = nxt, x = nx;
	}
	//cerr << "Finish\n";
}
struct info {
	int now, len;
	bool operator()(const info &a, const info &b) const {
		return a.len > b.len;
	}
};
void dij() {
	tree.init();
	fill(dp, dp+cnt, inf);
	priority_queue< info, vector<info>, info> pq;
	for (int id : start) {
		dp[id] = 0;
		pq.push({id, 0});
	}
	while (pq.size()) {
		auto [now, len] = pq.top();
		pq.pop();
		if (vis[now]) continue;
		vis[now] = true;
		auto [x, y] = to_loc[ now ];
		//cerr << "X Y waste " << x << ' ' << y << ' ' << len << '\n';
		for (auto [u, w] : edge[now]) {
			auto [nx, ny] = to_loc[u];
			tree.modify(x, nx+1, len);
			if (len + w < dp[u]) {
				dp[u] = len+w;
				pq.push({u, len+w});
			}
		}
	}
	for (int i = 1;i <= n;++i) {
		res[i] = tree.query(i);
		if (res[i] == inf) res[i] = -1;
	}
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0;i < n;++i)
		cin >> lb[i] >> rb[i], --lb[i], --rb[i];
	precal();
	for (int i = 0;i < m;++i)
		build(i);
	dij();
	for (int i = 1;i <= n;++i) {
		//cout << res[i] << '\n';
		if (res[i] == -1) cout << -1 << '\n';
		else cout << res[i] + i << '\n';
	}
}



Measured memory_bytes: 114684