#include<bits/stdc++.h>
using namespace std;

template<class Abel> struct RMQ_RAQ_STLP{//[0,STLP.n)
    vector<Abel> dat,lazy_val;
    vector<bool> lazy;
    long long n;
    Abel unity;

    RMQ_RAQ_STLP(long long n_origin, Abel SUM_UNITY){
        unity=SUM_UNITY;
        long long i=0;
        while(n_origin>(1<<i)) i++;
        n = (1<<i);
        dat.resize(2*n -1);
        lazy_val.resize(2*n-1);
        lazy.resize(2*n-1);
        for(i=0; i< 2*n -1; i++){
            dat[i]=SUM_UNITY;
            lazy_val[i]=SUM_UNITY;
            lazy[i]=0;
        }
    }

    void eval(long long k, long long l, long long r){
        if(lazy[k]==1){
            dat[k]+=lazy_val[k];
            if(r-l>1){
                lazy[k*2+1]=1;
                lazy[k*2+2]=1;
                lazy_val[k*2+1]+=lazy_val[k];
                lazy_val[k*2+2]+=lazy_val[k];
            }
            lazy[k]=0;
            lazy_val[k]=unity;
        }
    }

    void add_range(Abel x, long long a, long long b, long long k, long long l, long long r){//[a,b)
        eval(k,l,r);
        if(r<=a||b<=l) return;
        if(a<=l&&r<=b){
            lazy[k]=1;
            lazy_val[k]+=x;
            eval(k,l,r);
            return;
        }
        add_range(x,a,b,k*2+1, l, (l+r)/2);
        add_range(x,a,b,k*2+2, (l+r)/2, r);
        dat[k]=min(dat[k*2+1],dat[k*2+2]);
        return;
    }

    Abel min_range(long long a, long long b, long long k, long long l, long long r){//[a,b)
        eval(k,l,r);
        if(r<=a||b<=l) return 1000000000000000000;
        if(a<=l&&r<=b) return dat[k];
        Abel vl=min_range(a,b,k*2 +1, l, (l+r)/2);
        Abel vr=min_range(a,b,k*2 +2, (l+r)/2, r);
        return min(vl,vr);
    }
};

template<class Abel> struct RSQ_RUQ_STLP{//[0,STLP.n)
    vector<Abel> dat,lazy_val;
    vector<bool> lazy;
    long long n;
    Abel unity;

    RSQ_RUQ_STLP(long long n_origin, Abel SUM_UNITY){
        unity=SUM_UNITY;
        long long i=0;
        while(n_origin>(1<<i)) i++;
        n = (1<<i);
        dat.resize(2*n -1);
        lazy_val.resize(2*n-1);
        lazy.resize(2*n-1);
        for(i=0; i< 2*n -1; i++){
            dat[i]=SUM_UNITY;
            lazy_val[i]=SUM_UNITY;
            lazy[i]=0;
        }
    }

    void eval(long long k, long long l, long long r){
        if(lazy[k]==1){
            dat[k]=lazy_val[k];
            if(r-l>1){
                lazy[k*2+1]=1;
                lazy[k*2+2]=1;
                lazy_val[k*2+1]=lazy_val[k]/2;
                lazy_val[k*2+2]=lazy_val[k]/2;
            }
            lazy[k]=0;
            lazy_val[k]=unity;
        }
    }

    void update_range(Abel x, long long a, long long b, long long k, long long l, long long r){//[a,b)
        eval(k,l,r);
        if(r<=a||b<=l) return;
        if(a<=l&&r<=b){
            lazy[k]=1;
            lazy_val[k]=(r-l)*x;
            eval(k,l,r);
            return;
        }
        update_range(x,a,b,k*2+1, l, (l+r)/2);
        update_range(x,a,b,k*2+2, (l+r)/2, r);
        dat[k]=dat[k*2+1]+dat[k*2+2];
        return;
    }

    Abel sum_range(long long a, long long b, long long k, long long l, long long r){//[a,b)
        eval(k,l,r);
        if(r<=a||b<=l) return unity;
        if(a<=l&&r<=b) return dat[k];
        Abel vl=sum_range(a,b,k*2 +1, l, (l+r)/2);
        Abel vr=sum_range(a,b,k*2 +2, (l+r)/2, r);
        return vl+vr;
    }

    long long STLP_lower_bound(Abel val, long long a, long long b){//[a,b)
        long long a_origin=a;
        long long M;
        while(a<b-1){
            M=(a+b)/2;
            if(sum_range(a_origin,M+1,0,0,n)==val&&sum_range(a_origin,M,0,0,n)==val){
                b=M;
            }else if(sum_range(a_origin,M+1,0,0,n)>val){
                b=M;
            }else{
                a=M;
            }
        }
        return a;
    }
};

int main(){
    //input
    long long H,W;
    cin >> H >> W;
    long long A[H+1], B[H+1];
    long long i;
    for(i=1; i<=H; i++){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    //calc
    long long ans[H+1];
    RMQ_RAQ_STLP<long long> STLP_val(W,0);
    RSQ_RUQ_STLP<long long> STLP_num(W,0);
    STLP_num.update_range(1,0,W,0,0,STLP_num.n);
    long long val_L, num_L, val_R, num_R;
    for(i=1; i<=H; i++){
        if(B[i]<W-1){
            num_L=STLP_num.sum_range(A[i],B[i]+1,0,0,STLP_num.n);
            num_L=STLP_num.STLP_lower_bound(num_L,A[i],B[i]+1);
            val_L=STLP_val.min_range(num_L,num_L+1,0,0,STLP_val.n);
            num_R=B[i]+1;
            val_R=STLP_val.min_range(num_R,num_R+1,0,0,STLP_val.n);
            if(val_L<1000000&&val_L+(num_R-num_L)<val_R){                
                STLP_num.update_range(1,num_R,num_R+1,0,0,STLP_num.n);
                STLP_val.add_range((val_L+(num_R-num_L))-val_R,num_R,num_R+1,0,0,STLP_val.n);
            }
        }
        STLP_num.update_range(0,A[i],B[i]+1,0,0,STLP_num.n);
        STLP_val.add_range(1000000,A[i],B[i]+1,0,0,STLP_val.n);
        STLP_val.add_range(1,0,W,0,0,STLP_val.n);
        ans[i]=STLP_val.min_range(0,W,0,0,STLP_val.n);
    }

    //output
    for(i=1; i<=H; i++){
        if(ans[i]<1000000){
            cout << ans[i] << endl;
        }else{
            cout << -1 << endl;
        }
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 24648