// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#pragma region head
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vv = vector<vector<T>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrepi(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bit(n) (1LL << (n))
template <class T>
inline bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
const int INF = 1002003004;
const ll LINF = 1002003004005006007ll;
struct preprocess {
    preprocess() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} ____;
#pragma endregion head

#pragma region library
// Time Complexity: build O(N), query O(logN)
template <typename T, typename U>
struct LazySegmentTree {
    // T should be Monoid (Associativity, Identity element)
    using FuncTT = function<T(T, T)>;
    using FuncTU = function<T(T, U)>;
    using FuncUU = function<U(U, U)>;
    int sz, height;  // size of array
    vector<T> data;
    vector<U> lazy;  // 1-indexed(size: sz*2)
    T identity;      // identity element
    U identityLz;
    FuncTT f;
    FuncTU g;
    FuncUU h;

    // node k: parent k/2, children (2*k, 2*k+1)
    LazySegmentTree(int n, const T &identity, const U &identityLz,
                    FuncTT f, FuncTU g, FuncUU h)
        : identity(identity), identityLz(identityLz), f(f), g(g), h(h) {
        sz = 1;
        height = 0;
        while (sz < n) sz <<= 1, height++;
        data.assign(2 * sz, identity);
        lazy.assign(2 * sz, identityLz);
    }
    void set(int idx, const T &val) {
        data[idx + sz] = val;
    }
    void build() {
        for (int idx = sz - 1; idx > 0; idx--) {
            data[idx] = f(data[2 * idx], data[2 * idx + 1]);
        }
    }
    inline void evaluate(int idx) {
        if (lazy[idx] != identityLz) {
            if (idx < sz) {
                lazy[2 * idx] = h(lazy[2 * idx], lazy[idx]);
                lazy[2 * idx + 1] = h(lazy[2 * idx + 1], lazy[idx]);
            }
            data[idx] = reflect(idx);
            lazy[idx] = identityLz;
        }
    }
    inline T reflect(int idx) {
        if (lazy[idx] != identityLz)
            return g(data[idx], lazy[idx]);
        else
            return data[idx];
    }
    inline void thrust(int k) {
        for (int i = height; i > 0; i--) evaluate(k >> i);
    }
    void update(int a, int b, const U &x) { update(a, b, x, 1, 0, sz); }
    void update(int a, int b, const U &x, int idx, int l, int r) {
        evaluate(idx);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[idx] = h(lazy[idx], x);
            evaluate(idx);
        } else {
            update(a, b, x, 2 * idx, l, (l + r) / 2);
            update(a, b, x, 2 * idx + 1, (l + r) / 2, r);
            data[idx] = f(data[2 * idx], data[2 * idx + 1]);
        }
    }
    // [a, b)
    // recursive implementation
    T query(int a, int b) { return query(a, b, 1, 0, sz); }
    T query(int a, int b, int idx, int l, int r) {
        if (r <= a || b <= l) return identity;
        evaluate(idx);
        if (a <= l && r <= b)
            return data[idx];
        else {
            T vl = query(a, b, idx * 2, l, (l + r) / 2);
            T vr = query(a, b, idx * 2 + 1, (l + r) / 2, r);
            return f(vl, vr);
        }
    }
    // ToDo: for-loop implementation
    // T query(int l, int r)
    T operator[](const int &idx) {
        return query(idx, idx + 1);
    }

    // m : normally identity element
    // type : true(find_last), false(find_first)
    template <typename C>
    int find_subtree(int idx, const C &check, T &m, bool type) {
        while (idx < sz) {
            evaluate(idx);
            T nxt = type ? f(reflect(2 * idx + type), m) : f(m, reflect(2 * idx + type));
            if (check(nxt)) {
                idx = 2 * idx + type;
            } else {
                m = nxt;
                idx = 2 * idx + 1 - type;
            }
        }
        return idx - sz;
    }
    template <typename C>
    int find_first(int a, const C &check) {
        T L = identity;
        if (a <= 0) {
            if (check(f(L, reflect(1)))) return find_subtree(1, check, L, false);
            return -1;
        }
        thrust(a + sz);
        int b = sz;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) {
                T nxt = f(L, reflect(a));
                if (check(nxt)) return find_subtree(a, check, L, false);
                L = nxt;
                ++a;
            }
        }
        return -1;
    }

    template <typename C>
    int find_last(int b, const C &check) {
        T R = identity;
        if (b >= sz) {
            if (check(f(reflect(1), R))) return find_subtree(1, check, R, true);
            return -1;
        }
        thrust(b + sz - 1);
        int a = sz;
        for (b += sz; a < b; a >>= 1, b >>= 1) {
            if (b & 1) {
                T nxt = f(reflect(--b), R);
                if (check(nxt)) return find_subtree(b, check, R, true);
                R = nxt;
            }
        }
        return -1;
    }
};
#pragma endregion library
using ti = tuple<int, int, int, int, int>;
ti ff(ti a, ti b) {
    int a1, a2, a3, a4, a5, b1, b2, b3, b4, b5;
    tie(a1, a2, a3, a4, a5) = a;
    tie(b1, b2, b3, b4, b5) = b;
    int res1, res2, res3, res4, res5;
    res2 = max(a2, b2);
    res3 = min(a3, b3);
    res1 = res2 + res3;
    res4 = max(a4, b4);
    res5 = min(a5, b5);
    ti res = (ti){res1, res2, res3, res4, res5};
    return res;
}
ti fg(ti a, int x) {
    int &first = get<0>(a), &second = get<1>(a), &third = get<2>(a), &fourth = get<3>(a), &fifth = get<4>(a);
    first = max(first, x);
    fourth = max(fourth, x);
    fifth = max(fifth, x);
    if (third < first - second) third = first - second;
    return a;
}
int fh(int a, int b) {
    return max(a, b);
}
int main() {
    int h, w;
    cin >> h >> w;
    LazySegmentTree<ti, int> sg(w, (ti){INF, 0, INF, 0, INF}, 0, ff, fg, fh);
    rep(i, w) {
        sg.set(i, (ti){i + 1, i + 1, 0, i + 1, i + 1});
    }

    sg.build();

    rep(i, h) {
        int a, b;
        cin >> a >> b;
        int up = b + 1;
        if (b == w) up = INF;
        auto check1 = [a](ti t) { return get<3>(t) >= a; };
        auto check2 = [b](ti t) { return get<4>(t) <= b; };
        int ok = sg.find_first(0, check1);
        int ok2 = sg.find_last(INF, check2);
        sg.update(ok, ok2 + 1, up);
        int ans = get<2>(sg.query(0, w));
        if (ans >= w + 10)
            cout << -1 << '\n';
        else
            cout << ans + i + 1 << '\n';
    }
}


Measured memory_bytes: 15580