//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//省略
using vi  = vector<int>;
using vii = vector<vector<int>>;
using vl  = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

struct LazySegmentTree {
private:
    int n;
    vector<int> node, lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree(vector<int> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, INF);
        lazyFlag.resize(2*n-1, false);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    void lazyEvaluate(int k, int l, int r) {
        if(lazyFlag[k]) {
            node[k] = lazy[k];
            if(r - l > 1) {
                lazy[k*2+1] = lazy[k*2+2] = lazy[k];
                lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(int a, int b, int x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] = x;
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else {
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    int find(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return INF;
        if(a <= l && r <= b) return node[k];
        int vl = find(a, b, 2*k+1, l, (l+r)/2);
        int vr = find(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};



int main(){
    ll H,W;
    cin>>H>>W;

    map<ll,ll> idx;
    REP(i,W) idx[i+1]=i+1;
    LazySegmentTree seg(vi(W+5,0)),seg2(vi(W+5,0));

    REP2(i,1,W+1){
        seg.update(i,i+1,i);
    }


    vl ans(H);
    REP(i,H){
        ll l,r;
        cin>>l>>r;
        auto s=idx.lower_bound(l);
        auto e=idx.upper_bound(r);
        
        seg.update(s->second,e->second,r+1);
        
        ll id=INF;
        ll tmp=INF;
        for(auto itr=s;itr!=e;itr++){
            //distは始点から終点までの右方向距離
            ll dist=r+1-itr->second;
            if(dist<=tmp){
                tmp=dist;
                id=itr->second;
            }
        }
        seg2.update(s->second,e->second,INF);
        idx.erase(s,e);
        
        if(id!=INF&&r!=W){
            if(idx.count(r+1)){
                ll a=seg2.find(idx[r+1],idx[r+1]+1);
                ll b=tmp;
                if(tmp<=a){
                    idx[r+1]=id;
                    seg2.update(id,id+1,tmp);
                }
            }else{
                idx[r+1]=id;
                seg2.update(id,id+1,tmp);
            }
            
        }

        ll num=i+1+seg2.find(1,W+1);
        if(num>=INF) ans[i]=-1;
        else ans[i]=num;
    }
    REP(i,H) cout<<ans[i]<<endl;

    


}

Measured memory_bytes: 26228