#include<bits/stdc++.h>

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

#define fi first
#define se second
#define all(A) A.begin(),A.end()

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)
#define vv vector

//遅延セグ木
enum SegType{SUM,MIN,MAX};
template<typename T>
struct SegTree{
    int num=0, bt;
    vector<T> node, lazy;
    typedef function<T(const T &, const T &)> c1t;
    typedef function<T(const T &, const int &, const int &, const int &, const int &, const T &)> c2t;
    typedef function<T(const T &, const T &)> c3t;
    c1t calc1;c2t calc2;c3t calc3;T _init;

    void init(int num,T n,c1t calc1,c2t calc2,c3t calc3){
        int i = 0, j = 1;
        this->num = num;
        this->_init = n;
        this->calc1 = calc1;
        this->calc2 = calc2;
        this->calc3 = calc3;
        for (j = 1; j < num;)
            j *= 2;
        this->bt = j - 1;
        node.resize(j * 2 - 1, n);
        lazy.resize(j * 2 - 1, 0);
    }

    void init(int num,T n,SegType st){
        if(st==SegType::MAX){
            if(std::is_same<T,int>().value)
                _init = (T)INT_MIN;
            else if(std::is_same<T,long long>().value)
                _init = (T)LLONG_MIN;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return max(a, b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return a + n; },
                [](const T &a, const T &n) { return a + n; });
        }else if(st==SegType::MIN){
            if(std::is_same<T,int>().value)
                _init = (T)INT_MAX;
            else if(std::is_same<T, long long>().value)
                _init = (T)LLONG_MAX;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return min(a, b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return a + n; },
                [](const T &a, const T &n) { return a + n; });
        }else if(st==SegType::SUM){
            if(std::is_same<T,int>().value)
                _init = (T)0;
            else if(std::is_same<T,long long>().value)
                _init = (T)0;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return (a + b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return (a + (r - l + 1) * n); },
                [](const T &a, const T &n) { return (a + n / 2); });
        }
    }
    void addd(int x,int y,T n){
        if(x>y)
            return;
        _addd(x, y, n, 0, 0, this->bt);
    }
    void _addd(const int& x,const int& y,const T& n,int p,int l,int r){
        if (r < x || y < l)
            return;
        if(x<=l&&r<=y){
            lazy[p] = calc2(lazy[p], x, y, l, r, n);
            evall(p);
        }else{
            if(lazy[p]!=0)
                evall(p);
            _addd(x, y, n, p * 2 + 1, l, (l + r) / 2);
            _addd(x, y, n, p * 2 + 2, (l + r) / 2 + 1, r);
            node[p] = calc1(node[p * 2 + 1], node[p * 2 + 2]);
        }
    }
    inline void evall(int x){
        node[x] += lazy[x];
        if(x<bt){
            lazy[x * 2 + 1] = calc3(lazy[x * 2 + 1], lazy[x]);
            lazy[x * 2 + 2] = calc3(lazy[x * 2 + 2], lazy[x]);
        }
        lazy[x] = 0;
    }
    void sett(int x,T n){
        gett(x);
        int i = bt+x;
        node[i] = n;
        while(i!=0){
            i = (i - 1) / 2;
            node[i] = calc1(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }
    inline T gett(int x){
        T ret=_init;
        _gett(x, x, 0, 0, this->bt, ret);
        return ret;
    }
    T gett(int x,int y){
        T ret=_init;
        if(x>y)
            return ret;
        _gett(x, y, 0, 0, this->bt, ret);
        return ret;
    }
    void _gett(const int& x,const int& y,int p,int l,int r,T& ret){
        if(r<x||y<l)
            return;
        if(lazy[p]!=0)
            evall(p);
        if(x<=l&&r<=y){
            ret = calc1(ret, node[p]);
            return;
        }
        _gett(x, y, p * 2 + 1, l, (l + r) / 2, ret);
        _gett(x, y, p * 2 + 2, (l + r) / 2 + 1, r, ret);
    }
};

const ll HWMX=202020;
ll H,W;

ll i, j, k;


ll anscalc(ll h, ll w, ll i){
    if(i==0)
        return 1e9;
    return h - 1 + (w - i);
}

int main(){

    scanf("%lld%lld", &H,&W);
    priority_queue<pll> pqa,pqb;
    pqa.push({-1e9,1e9});
    pqb.push({-1e9,1e9});
    rep(i,0,H){
        ll a, b;
        scanf("%lld%lld", &a, &b);
        pqa.push({-a, i + 1});
        pqb.push({-b, i + 1});
    }

    SegTree<ll> sg;
    sg.init(HWMX, 0, SegType::MAX);
    set<ll> st;
    vv<ll> ans(HWMX,1e9);
    st.insert(0);
    st.insert(H + 1);

    rep(i,1,W+1){
        //printf("%lld ", i);
        while(-pqa.top().fi==i){
            st.insert(pqa.top().se);
            pqa.pop();
        }
        while(-pqb.top().fi<i){
            ll a = pqb.top().se;
            pqb.pop();

            st.erase(a);
            auto ita = st.lower_bound(a);
            ll bdn = *ita;
            --ita;
            ll bup = *ita;
            ll c = sg.gett(bup + 1, bdn);
            sg.sett(bdn, c);
            ans[bdn] = min(ans[bdn],anscalc(bdn, i, c));
            
        }

        

        ll a = *st.lower_bound(1);
        //printf("\n%lld <- ", a);
        sg.sett(a, i);
        ans[a] = min(ans[a], anscalc(a, i, i));

        //for(auto a:st){
        //    printf("%lld ", a);
        //}
        
        //printf("\n%lld:\n", i);
        //cout << pqa.size() << " " << 
        //    pqb.size() << " " <<
        //    st.size()<< endl;
        
        //rep(k,1,H+2){
        //    printf("%lld,%lld ", ans[k],sg.gett(k));
        //}
        
    }

    
    j = 0;
    for (i = H + 1; i > 0;--i){
        ans[i - 1] = min(ans[i - 1], ans[i] - 1);
    }
    rep(i,2,H+2){
        printf("%lld\n", ans[i] > 1e8 ? -1 : ans[i]);
    }

    return 0;
}

Measured memory_bytes: 28416