#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
using namespace std;
#define _LL long long
#define rep(i, n) for (_LL i = 0; i < (_LL)(n); i++)
#define vecrep(itr, v) for (auto itr = (v).begin(); itr != (v).end(); itr++)

// ライブラリテスト
template<class T> class SegTreeDelaySkelton
{
    private:
        int _n;
        int _d;
        int _bit;
        T* nodes;
        bool *_used;
        // 子に伝搬する情報があるか
        bool *_last;

        // leftとrightでparentを更新。left, rightにNULLが入ることも。[indexl, indexr)までがparentの担当
        void (*_update)(T* parent, T* left, T* right, int indexl, int indexr);

        // nodeをvで更新する。（親への伝搬はクラス内で処理）
        void (*_rangef)(T* node, T *v, int indexl, int indexr);

        void (*_get)(T* node, T *ret, int l);

    public:
        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int) )
        {
            construct(n, update, f);
        }

        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int), T def)
        {
            construct(n, update, f);
            for(int i = 0; i < n; i++ ) nodes[_bit + i] = def;
            for(int i = _bit - 1; i >= 0; i-- ) 
                if(_used[i]) callupdate(i);
        }

        void setGet( void (*get)(T*, T*, int) )
        {
            _get = get;
        }

        void set(int index, T& value)
        {
            _rangef( nodes + (_bit + index), &value, index, index + 1 );
            updatenode((_bit + index) / 2);
        }

        void updatenode(int i)
        {
            callupdate(i);
            if( i > 1) updatenode( i / 2 );
        }

        T* top() { return nodes + 1;}
        T get(int l) { return getsub(1, l); }

        void range(int l, int r, T* v)
        {
            rangeSub(l, r, v, 1);
        }

        ~SegTreeDelaySkelton()
        {
            delete nodes;
            delete _used;
        }
    private:

        T* getnode(int i)
        {
            return _used[i] ? nodes + i : NULL;
        }

        T getsub(int index, int l)
        {
            if( index >= _bit ) return nodes[index];
            int nodel, noder, nodec;
            getindex(index, nodel, noder);
            nodec = (nodel + noder) / 2;             
            if( _last[index] )
            {
                if( _get == NULL ) return nodes[index];
                T ret = getsub(l < nodec ? (index * 2) : (index * 2 + 1), l);
                _get(nodes + index, &ret, l);
                return ret;
            }
            return getsub(l < nodec ? (index * 2) : (index * 2 + 1), l);
        }        

        void callupdate(int i)
        {
            int nodel, noder;
            getindex(i, nodel, noder);

            int t = i; int topd = 1;
            while( t > 1 ) { topd = (topd << 1); t = ( t >> 1);}
            int no = i - topd;
            int k = _bit / topd;            
            _update(nodes + i, getnode(i * 2), getnode(i * 2 + 1), nodel, noder);
        }

        void construct(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int))
        {
            _get = NULL;
            _update = update;
            _rangef = f;
            _n = n;
            _d = 1;
            _bit = 1;
            while( _bit < _n )
            {
                _bit *= 2;
                _d++;
            }
            nodes = new T[_bit * 2];
            _used = new bool[_bit * 2];
            _last = new bool[_bit * 2];
            for(int i = 0; i < _bit * 2; i++ ) _last[i] = false;
            for(int i = 0; i < n; i++ ) _used[_bit + i] = true;
            for(int i = _bit - 1; i > 0; i-- ) _used[i] = (_used[i * 2] || _used[i * 2 + 1]);
        }

        void getindex(int i, int &nodel, int &noder)
        {
            int t = i; int topd = 1;
            while( t > 1 ) { topd = (topd << 1); t = ( t >> 1);}
            int no = i - topd;
            int k = _bit / topd;    
            nodel = k * no;
            noder = k * (no + 1);   
        }

        void rangeSub(int l, int r, T *v, int index)
        {
            int nodel, noder, nodec;
            getindex(index, nodel, noder);
            nodec = nodel + (noder - nodel) / 2;
            if( noder - nodel <= 1 || (l <= nodel && r >= noder) ) { _last[index] = true; _rangef(nodes + index, v, nodel, noder); return;}
            // 伝搬
            if(  _last[index] )
            {
                if( _used[index * 2]) { _rangef(nodes + index * 2, nodes + index, nodel, nodec); _last[index * 2] = true; }
                if( _used[index * 2 + 1]) {_rangef(nodes + index * 2 + 1, nodes + index, nodec, noder); _last[index * 2 + 1] = true; }
            }
            _last[index] = false;

            if( l < nodec && r > nodel ) rangeSub(l, r, v, index * 2);
            if( r > nodec && l < noder ) rangeSub(l, r, v, index * 2 + 1);
            _update(nodes + index, getnode(index * 2), getnode(index * 2 + 1), nodel, noder);
        }        
};

struct MyNode
{
    int value;
    int ans;

    MyNode() { value = 0; ans = 0; }
};


void update(MyNode* parent, MyNode* left, MyNode* right, int indexl, int indexr)
{
    if( right == NULL )
    {
        parent->ans = left->ans;
    }
    else if( left == NULL )
    {
        parent->ans = right->ans;
    }
    else
    {    
        parent->ans = min(left->ans, right->ans);
    }
}

void setrange(MyNode* node, MyNode *v, int indexl, int indexr)
{
    node->value = v->value;
    node->ans = indexl - v->value;
}



int main()
{
    int h, w; cin >> h >> w;
    SegTreeDelaySkelton<MyNode> st(w, update, setrange);
    MyNode node;
    node.ans = 0;
    rep(i, w) { node.value = i; st.set(i, node);}
    rep(i, h)
    {
        int a, b; cin >> a >> b; a--; b--;
        int r = -w * 2;
        MyNode node;
        node.value = -w * 2;
        if( a > 0 ) node.value = st.get(a - 1).value;
        st.range(a, b + 1, &node);
#if 0        
        cout << i << ":" << endl;
        rep(j, w) cout << st.get(j) << " ";
        cout << endl;
        rep(j, w) cout << st.getmin(j, j + 1) << " ";
        cout << endl;
#endif
        int ret = st.top()->ans;
        if( ret > w )
        {
            cout << -1 << endl;
        }
        else
        {
            cout << ret + i + 1 << endl;
        }
    }
    return 0;    
}

Measured memory_bytes: 8464