#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) x
#define WATCH(x) TRACE( cout << #x" = " << x << endl)
#define PRINT(x) TRACE(printf(x))
#define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})
#define rep(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define trav(a, x) for(auto& a : x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) static_cast<int>(x.size())
#define mp make_pair
#define fi first
#define se second

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

void buff() { ios::sync_with_stdio(false); cin.tie(nullptr); }

constexpr ll MOD = 1e9 + 7;

inline ll pow_mod(ll a, ll b, ll mod = MOD) {
    ll res = 1; a %= mod; assert(b >= 0);
    for(;b;b>>=1) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

template<typename T> inline void remin(T& x, const T& y) { x = min(x, y); }
template<typename T> inline void remax(T& x, const T& y) { x = max(x, y); }

template<typename T> ostream& operator<<(ostream &os, const vector<T>& v) {
    os << "{"; string sep; for(const auto& x : v) os << sep << x, sep = ", "; return os << "}"; 
}

template<typename T, size_t size> ostream& operator<<(ostream& os, const array<T, size>& arr) {
    os << "{"; string sep; for(const auto& x : arr) os << sep << x, sep = ", "; return os << "}"; 
}

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { 
    return os << '(' << p.first << ", " << p.second << ')'; 
}

constexpr int inf = 1e9;
constexpr int ms = 2e5 + 13;

pii swp(const pii& a) {
    return make_pair(a.second, a.first);
}

struct interval_union {
    set< pair<int, int> > L, R;
    multiset<long long> query;
    map< pair<int, int>, int > value;
    interval_union() {} 
    void add(pair<int, int> x, ll y) {
        query.insert(y);
        value[x] = y;
        L.insert(x);
        R.insert(swp(x)); 
    }

    void rem(pair<int, int> x, ll y) {
        query.erase(query.find(y));
        L.erase(x);
        R.erase(swp(x));
        value.erase(x);
    }

    ll min_value() { return *query.begin(); }
    
    vector< pair<int, int> > intersect(pair<int, int> x) {
        auto use1 = make_pair(x.first, -inf);
        auto use2 = make_pair(x.second, inf);
        auto it1 = L.lower_bound(use1);
        auto it2 = R.lower_bound(use2);
        set< pair<int, int> > bad;
        vector< pair<int, int> > ret;

        // Tratando o caso de (x) estar inteiramente contido em um range
        if(it2 != R.end()) {
            int lo = (*it2).second, hi = (*it2).first;
            if(lo <= x.first && x.second <= hi) {
                ret.emplace_back(lo, hi);
                return ret;
            }
        }

        if(it1 != L.end()) {
            while(it1 != L.end()) {
                auto val = *it1;
                if(val.first <= x.second) bad.insert(val);
                else break;
                it1 = next(it1);
            }
        }

        if(it2 != R.begin()) {
            it2 = prev(it2);
            while(1) {
                auto val = *it2;
                if(val.first >= x.first) bad.insert(swp(val));
                else break;
                if(it2 == R.begin()) break;
                it2 = prev(it2);
            }
        }
        for(auto b : bad) ret.emplace_back(b);
        return ret;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector<int> l(h), r(h);
    auto UNI = interval_union();
    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 lft = l[i - 1], rgt = r[i - 1];
        vector< pair<int, int> > ivals = UNI.intersect(make_pair(lft, rgt));
        ll st = inf;
        pair<int, int> beg = make_pair(inf, inf);
        ll beg_val = -1;
        if(ivals[0].first < lft) {
            st = UNI.value[ivals[0]] + lft - ivals[0].first;
            beg = make_pair(ivals[0].first, lft - 1);
            beg_val = UNI.value[ivals[0]];
        }
        else {
            if(lft != 0) {
                auto bef = *(UNI.R).lower_bound(make_pair(lft - 1, -inf));
                st = UNI.value[swp(bef)] + lft - bef.second;
            }
        }
        pair<int, int> fin = make_pair(inf, inf);
        ll fin_val = -1;
        if(ivals.back().second != rgt) {
            fin = make_pair(rgt + 1, ivals.back().second);
            fin_val = UNI.value[ivals.back()] + rgt + 1 - ivals.back().first;
        }
        for(auto x : ivals) UNI.rem(x, UNI.value[x]);
        UNI.add(make_pair(lft, rgt), 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: 45616