// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


// doc: https://shibh308.github.io/library/library/lib/classes/lazysegtree.cpp.html
template<typename T, typename U>
struct Segtree{
    int n;
    T op_t;
    U op_u;
    vector<T> elm;
    vector<U> lazy;
    vector<int> length;
    function<T(T, T)> f;
    function<T(T, U, int)> g;
    function<U(U, U)> h;

    Segtree(int n, T init, function<T(T, T)> f, function<T(T, U, int)> g, function<U(U, U)> h, T op_t = T(), U op_u = U()) :
            n(n),
            op_t(op_t),
            op_u(op_u),
            elm(2 * n, init),
            lazy(2 * n, op_u),
            length(2 * n, 0),
            f(f),
            g(g),
            h(h)
    {
        for(int i = n - 1; i > 0; --i){
            elm[i] = f(elm[2 * i], elm[2 * i + 1]);
            length[i] = length[2 * i] + 1;
        }
    }

    Segtree(int n, vector<T> init, function<T(T, T)> f, function<T(T, U, int)> g, function<U(U, U)> h, T op_t = T(), U op_u = U()) :
            n(n),
            op_t(op_t),
            op_u(op_u),
            elm(2 * n),
            lazy(2 * n, op_u),
            length(2 * n, 0),
            f(f),
            g(g),
            h(h)
    {
        for(int i = 0; i < n; ++i)
            elm[i + n] = init[i];

        for(int i = n - 1; i > 0; --i){
            elm[i] = f(elm[2 * i], elm[2 * i + 1]);
            length[i] = length[2 * i] + 1;
        }
    }

    vector<int> get_list(int x, int y){

        vector<int> ret_list;
        for(x += n, y += n - 1; x; x >>= 1, y >>= 1){
            ret_list.emplace_back(x);
            if(x != y)
                ret_list.emplace_back(y);
        }

        return ret_list;
    }

    void eval(int x){

        elm[x] = g(elm[x], lazy[x], 1 << length[x]);
        if(x < n){
            lazy[2 * x] = h(lazy[2 * x], lazy[x]);
            lazy[2 * x + 1] = h(lazy[2 * x + 1], lazy[x] + length[2 * x + 1]);
        }
        lazy[x] = op_u;
    }

    void update(int x, int y, U val){

        if(x == y)
            return;
        vector<int> index_list = get_list(x, y);
        for(int i = index_list.size() - 1; i >= 0; --i)
            eval(index_list[i]);

        for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){
            if(x & 1){
                lazy[x] = h(lazy[x], val);
                eval(x++);
            }
            if(!(y & 1)){
                lazy[y] = h(lazy[y], val);
                eval(y--);
            }
        }

        for(auto index : index_list){
            if(index < n){
                eval(2 * index);
                eval(2 * index + 1);
                elm[index] = f(elm[2 * index], elm[2 * index + 1]);
            }
        }
    }

    T get(int x, int y){

        vector<int> index_list = get_list(x, y);
        for(int i = index_list.size() - 1; i >= 0; --i)
            eval(index_list[i]);

        T l = op_t, r = op_t;
        for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){
            if(x & 1){
                eval(x);
                l = f(l, elm[x++]);
            }
            if(!(y & 1)){
                eval(y);
                r = f(elm[y--], r);
            }
        }
        return f(l, r);
    }
};

vector<i64> solve2(long long h, long long w, std::vector<long long> a, std::vector<long long> b){
    vector<vector<i64>> dp(h + 1, vector<i64>(w, INF));
    for(int i = 0; i < w; ++i)
        dp[0][i] = 0;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(j != w - 1)
                chmin(dp[i][j + 1], dp[i][j] + 1);
            if(a[i] - 1 <= j && j < b[i])
                continue;
            chmin(dp[i + 1][j], dp[i][j] + 1);
        }
    }
    vector<i64> ans(h);
    for(int i = 0; i < h; ++i){
        ans[i] = *min_element(dp[i + 1].begin(), dp[i + 1].end());
        if(ans[i] >= INF)
            ans[i] = -1;
    }
    return ans;
}


vector<i64> solve(long long h, long long w, std::vector<long long> a, std::vector<long long> b){
    vector<i64> ans;
    for(int i = 0; i < h; ++i)
        --a[i];
    set<pair<int,i64>> s;
    set<pair<i64,int>> s2;
    for(int i = 0; i < w; ++i){
        s.emplace(i, 0);
        s2.emplace(0, i);
    }
    for(int i = 0; i < h; ++i){
        auto l = s.lower_bound(make_pair(a[i], -INF));
        auto r = s.lower_bound(make_pair(b[i], -INF));
        i64 val = (r == s.begin() ? INF : prev(r)->second + (b[i] - prev(r)->first));
        for(auto iter = l; iter != r;){
            s2.erase(make_pair(iter->second, iter->first));
            iter = s.erase(iter);
        }
        if(b[i] != w && !(r != s.end() && r->first == b[i])){
            s.emplace(b[i], val);
            s2.emplace(val, b[i]);
        }
        assert(s.size() == s2.size());

        ans.emplace_back(s2.empty() ? -1 : (s2.begin()->first) + i + 1);
        if(ans.back() >= 1e9)
            ans.back() = -1;
    }
    return ans;
}

void check(){
    int H = random() % 10 + 1;
    int W = random() % 10 + 1;
    vector<i64> A(H), B(H);
    for(int i = 0; i < H; ++i){
        A[i] = rand() % W + 1;
        B[i] = rand() % W + 1;
        if(A[i] > B[i])
            swap(A[i], B[i]);
    }
    auto res = solve(H, W, A, B);
    auto res2 = solve2(H, W, A, B);
    for(int i = 0; i < res.size(); ++i){
        if(res[i] != res2[i]){
            cout << "h:" << H << " w:" << W << endl;
            for(int j = 0; j < H; ++j)
                cout << A[j] << " " << B[j] << endl;
            cout << "correct:";
            for(int j = 0; j < res.size(); ++j)
                cout << res2[j] << " \n"[j == res.size() - 1];
            cout << "predict:";
            for(int j = 0; j < res.size(); ++j)
                cout << res[j] << " \n"[j == res.size() - 1];
            cout << endl;
            break;
        }
    }
}

signed main(){
    long long H;
    scanf("%lld", & H);
    long long W;
    scanf("%lld", & W);
    std::vector<long long> A(H);
    std::vector<long long> B(H);
    for(int i = 0; i < H; i++){
        scanf("%lld", & A[i]);
        scanf("%lld", & B[i]);
    }
    auto res = solve(H, W, A, B);
    for(int i = 0; i < H; ++i)
        cout << res[i] << endl;
}



Measured memory_bytes: 36512