#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

vi solve(int h, int w, vector<pii> lr) {
    using P1 = pair<int, pii>;
    using P2 = pair<pii, int>;
    set<P1> sij;
    set<P2> jis;
    rep (i, w) {
        if (i < lr[0].first or i >= lr[0].second) {
            sij.insert(P1(0, pii(0, i)));
            jis.insert(P2(pii(i, 0), 0));
        }
    }

    vi res;
    for (int i = 1; i <= h; i++) {
        if (sij.size() == 0) {
            cout << -1 << endl;
            res.push_back(-1);
            continue;
        }
        auto temp = *sij.begin();
        // DEBUG(temp);
        cout << temp.first + i << endl;
        res.push_back(temp.first + i);
        if (i == h) break;

        int l = lr[i].first, r = lr[i].second;
        int min_score = inf;
        while (true) {
            auto itr = jis.lower_bound(P2(pii(l, -inf), -inf));
            if (itr == jis.end()) break;
            if (itr->first.first > r) break;
            P2 temp = *itr;
            int pre_score = temp.second;
            int i0 = temp.first.second, j0 = temp.first.first;
            P1 aikata = P1(pre_score - i0, pii(i0, j0));
            chmin(min_score, pre_score + (i - i0) + (r - j0));
            jis.erase(itr);
            sij.erase(aikata);
        }
        if (min_score != inf and r < w) {
            jis.insert(P2(pii(r, i), min_score));
            sij.insert(P1(min_score - i, pii(i, r)));
        }
    }
    return res;
}

vi solve2(int h, int w, vector<pii> lr) {
    vector<vector<bool>> a(h + 1, vector<bool>(w, true));
    rep (i, h) {
        for (int j = lr[i].first; j < lr[i].second; j++) {
            a[i][j] = false;
        }
    }

    vii dist(h + 1, vi(w, inf));
    queue<pii> qu;
    rep (j, w) {
        dist[0][j] = 0;
        qu.push(pii(0, j));
    }

    while (qu.size()) {
        pii temp = qu.front();
        qu.pop();
        int i = temp.first, j = temp.second;
        int score = dist[i][j];
        if (i < h and a[i][j]) {
            int ni = i + 1, nj = j;
            if (dist[ni][nj] > dist[i][j] + 1) {
                dist[ni][nj] = dist[i][j] + 1;
                qu.push(pii(ni, nj));
            }
        }
        if (j < w - 1) {
            int ni = i, nj = j + 1;
            if (dist[ni][nj] > dist[i][j] + 1) {
                dist[ni][nj] = dist[i][j] + 1;
                qu.push(pii(ni, nj));
            }
        }
    }

    vector<int> res;
    for (int i = 1; i <= h; i++) {
        int mi = inf;
        rep (j, w) {
            chmin(mi, dist[i][j]);
        }
        if (mi == inf) res.push_back(-1);
        else res.push_back(mi);
    }
    return res;
}

struct dice {
  mt19937 mt;
  dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
  // [0, x)の一様乱数
  ll operator()(ll x) { return this->operator()(0, x); }
  // [x, y)の一様乱数
  ll operator()(ll x, ll y) {
    uniform_int_distribution<ll> dist(x, y - 1);
    return dist(mt);
  }
  vl operator()(int n, ll x, ll y) {
    vl res(n);
    for (int i = 0; i < n; i++) res[i] = this->operator()(x, y);
    return res;
  }
} rnd;

signed main() {
    fio();
    int h, w;
    cin >> h >> w;
    // h = w = 4;

    // while (true) {
    vector<pii> lr(h);
    rep (i, h) {
        cin >> lr[i].first >> lr[i].second;
        // lr[i].first = rnd(1, w + 1); lr[i].second = rnd(lr[i].first, w + 1);
        lr[i].first--;
    }
    // DEBUG_VEC(lr);

    vi res1 = solve(h, w, lr);
    // vi res2 = solve2(h, w, lr);
    // DEBUG_VEC(res1);
    // DEBUG_VEC(res2);
    // assert(res1 == res2);
    // }
}

Measured memory_bytes: 36692