#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;
const int MAX = 2e5 + 5;
struct interval_union {
    set<pair<int, int>> le, ri;
    multiset<ll> query;
    map<pair<int, int>, int> value;
    void add(pair<int, int> x, ll y) {
        query.insert(y);
        value[x] = y;
        le.insert(x); ri.insert(make_pair(x.second, x.first));
    }
    void rem(pair<int, int> x, ll y) {
        query.erase(query.find(y));
        le.erase(x); ri.erase(make_pair(x.second, x.first));
        value.erase(x);
    }
    ll min_value() { return *query.begin(); }
    vector<pair<int, int>> intersect(pair<int, int> x) {
        pair<int, int> use1 = make_pair(x.first, -INF);
        pair<int, int> use2 = make_pair(x.second, INF);
        auto it1 = le.lower_bound(use1);
        auto it2 = ri.lower_bound(use2);
        set<pair<int, int>> bad;
        vector<pair<int, int>> ret;
        if (it2 != ri.end()) {
            int lo = (*it2).second, hi = (*it2).first;
            if (lo <= x.first && x.second <= hi) {
                ret.emplace_back(lo, hi);
                return ret;
            }
        }
        if (it1 != le.end()) {
            while (it1 != le.end()) {
                auto val = (*it1);
                if (val.first <= x.second) bad.insert(val);
                else break;
                it1 = next(it1);
            }
        }
        if (it2 != ri.begin()) {
            it2 = prev(it2);
            while (true) {
                auto val = (*it2);
                if (val.first >= x.first) bad.insert(make_pair(val.second, val.first));
                else break;
                if (it2 == ri.begin()) break;
                it2 = prev(it2);
            }
        }
        for (auto b: bad) ret.emplace_back(b);
        return ret;
    }
} uni;
int l[MAX], r[MAX];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int h, w; cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> l[i] >> r[i];
        l[i]--, r[i]--;
    }
    for (int i = 0; i < w; i++) uni.add(make_pair(i, i), 0);
    for (int i = 1; i <= h; i++) {
        int L = l[i-1], R = r[i-1];
        vector<pair<int, int>> ivals = uni.intersect(make_pair(L, R));
        ll st = INF;
        pair<int, int> beg = make_pair(INF, INF);
        ll beg_val = -1;
        if (ivals[0].first < L) {
            st = uni.value[ivals[0]] + L - ivals[0].first;
            beg = make_pair(ivals[0].first, L - 1);
            beg_val = uni.value[ivals[0]];
        } else {
            if (L != 0) {
                auto bef = *(uni.ri).lower_bound(make_pair(L - 1, -INF));
                st = uni.value[make_pair(bef.second, bef.first)] + L - bef.second;
            }
        }
        pair<int, int> fin = make_pair(INF, INF);
        ll fin_val = -1;
        if (ivals.back().second != R) {
            fin = make_pair(R+1, ivals.back().second);
            fin_val = uni.value[ivals.back()] + R + 1 - ivals.back().first;
        }
        for (auto x: ivals) uni.rem(x, uni.value[x]);
        uni.add(make_pair(L, R), st);
        if (beg_val != -1) uni.add(beg, beg_val);
        if (fin_val != -1) uni.add(fin, fin_val);
        ll res = uni.min_value() + i;
        if (res >= INF) cout << -1 << '\n';
        else cout << res << '\n';
    }
    return 0;
}


Measured memory_bytes: 45928