#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

pll operator+(pll a,pll b){
  return pll(a.first+b.first,a.second+b.second);
}
pll operator-(pll a,pll b){
  return pll(a.first-b.first,a.second-b.second);
}
pll operator*(ll a,pll b){
  return pll(b.first*a,b.second*a);
}
const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

template<typename T>
vector<T> build_segtree(function<T(T,T)>f,T unit,const vector<T> &v){
    size_t n=1;
    while(n<v.size()){n<<=1;}
    vector<T> tree(n<<1,unit);
    for(size_t i=0;i<v.size();++i)tree[n+i]=v[i];
    if(n>0)for(size_t i=n-1;i;--i){
        tree[i]=f(tree[i*2],tree[i*2+1]);
    }
    return tree;
}
template <typename T>
class segtree{
    using F = function<T(T,T)>;
    size_t n;
    F f;
    T unit;
    vector<T> tree;
    public:
    segtree(F f,T unit,const vector<T> &v):f(f),unit(unit),tree(){
        tree=build_segtree(f,unit,v);
        n = tree.size()/2;
    }
    segtree(F f,T unit,size_t n_):segtree(f,unit,vector<T>(n_,unit)){
    }
    void build(const vector<T> &v){
        for(size_t i=0;i<v.size();++i)tree[n+i]=v[i];
        if(n>0)for(size_t i=n-1;i;--i){
            tree[i]=f(tree[i*2],tree[i*2+1]);
        }
    }
    void set_val(size_t k,T x){
        if(k>n){
            cerr<<"out of size"<<endl;
            exit(1);
        }
        tree[k+=n]=x;
        while(k>>=1){
            tree[k]=f(tree[k*2],tree[k*2+1]);
        }
    }
    T get_val(size_t k){
        return this->query(k,k+1);
    }
    void add_val(size_t k,T x){
        if(k>n){
            cerr<<"out of size"<<endl;
            exit(1);
        }
        k+=n;
        tree[k]=f(tree[k],x);
        while(k>>=1){
            tree[k]=f(tree[k*2],tree[k*2+1]);
        }
    }
    T query(size_t a,size_t b){
        //[a,b)
        if(a>n){
            a=n;
        }
        if(b>n){
            b=n;
        }
        T vl=unit,vr=unit;
        for(size_t l=a+n,r=b+n;l<r;l/=2,r/=2){
            if(l&1)vl=f(vl,tree[l++]);
            if(r&1)vr=f(tree[--r],vr);
        }
        return f(vl,vr);
    }
};
void solve(long long H, long long W, std::vector<long long> A, std::vector<long long> B){
  ll cur=0;
  ll ans=0;
  map<ll,ll> s;
  vector<pll>v;
  REP(W){
    v.push_back(pll(i,i));
  }
  auto f=[](ll x,ll y){return min(x,y);};
  segtree<ll> st(f,INF,W);
  REP(W){
    s[i]=i;
    st.set_val(i,0);
  }
  REP(H){
    auto itr=s.lower_bound(A[i]);
    ll x=-INF;
    while(itr!=s.end()&&itr->first<=B[i]){
      st.set_val(itr->first,INF);
      chmax(x,itr->second);
      s.erase(itr++);
    }
    ll r=B[i]+1;
    if(x!=-INF&&B[i]!=W-1){
      if(s.count(r)==0)s[r]=-INF;
      chmax(s[r],x);
      st.set_val(r,r-s[r]);
    }
    ll ans=st.query(0,W)+i+1;
    if(ans>H+W){
      ans=-1;
    }
    cout<<ans<<endl;
  }
}

int main(){
  cout<<setprecision(1000);
    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]);
        --A[i];--B[i];
    }
    solve(H, W, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 26156