#include <bits/stdc++.h>
#define inf (int)(1e8)
using namespace std;

// 0-indexed
template <class T, class E>
struct SegmentTreeLaze {
  // a,b:T c,d:E e:E(unit)
  // g(f(a,b),c) = f(g(a,c),g(b,c))
  // g(g(a,c),d) = g(a,h(c,d))
  // g(a,e) = a
  typedef function<T(T, T)> F;
  typedef function<T(T, E)> G;
  typedef function<E(E, E)> H;
  int n, height;
  F f;
  G g;
  H h;
  T tunit;
  E eunit;
  vector<T> dat;
  vector<E> laz;
  SegmentTreeLaze(){};
  SegmentTreeLaze(int newn, F f, G g, H h, T nt, E ne)
      : f(f), g(g), h(h), tunit(nt), eunit(ne) {
    init(newn);
  }
  SegmentTreeLaze(const vector<T> &v, F f, G g, H h, T nt, E ne)
      : f(f), g(g), h(h), tunit(nt), eunit(ne) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1, height = 0;
    while (n < newn) n <<= 1, ++height;
    dat.assign(n << 1, tunit);
    laz.assign(n << 1, eunit);
  }

  inline T reflect(int k) {
    return laz[k] == eunit ? dat[k] : g(dat[k], laz[k]);
  }

  inline void eval(int k) {
    if (laz[k] == eunit) return;
    laz[k << 1] = h(laz[k << 1], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = eunit;
  }

  inline void thrust(int k) {
    for (int i = height; i; --i) eval(k >> i);
    // reset query
    dat[k] = reflect(k);
    laz[k] = eunit;
  }

  void recalc(int k) {
    while (k >>= 1) dat[k] = f(reflect(k << 1), reflect((k << 1) | 1));
  }
  // [a,b)
  void update(int a, int b, E newdata) {
    thrust(a += n);
    thrust(b += n - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) laz[l] = h(laz[l], newdata), l++;
      if (r & 1) --r, laz[r] = h(laz[r], newdata);
    }
    recalc(a);
    recalc(b);
  }

  void set_val(int k, T newdata) {
    thrust(k += n);
    dat[k] = newdata;
    laz[k] = eunit;
    recalc(k);
  }

  // [a,b)
  T query(int a, int b) {
    thrust(a += n);
    thrust(b += n - 1);
    T vl = tunit, vr = tunit;
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, reflect(l++));
      if (r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};

using P = pair<int, int>;

struct dat {
  bool re;
  P p;
  dat(bool _r = 0) : re(_r), p(inf, -1) {}
  dat(bool _r, P _p) : re(_r), p(_p) {}
  bool operator==(const dat &r) const { return re == r.re && p == r.p; }
};

int h, w;
SegmentTreeLaze<P, dat> seg1, seg2;
vector<P> v;

int main() {
  cin >> h >> w;
  v.assign(h + 1, P(0, 0));
  for (int i = 0; i < h; ++i) {
    cin >> v[i].first >> v[i].second;
    --v[i].first;
  }
  {
    vector<P> tmp(w);
    for (int i = 0; i < w; ++i) {
      tmp[i].first = (v[0].first <= i && i < v[0].second) * inf;
      tmp[i].second = i;
    }
    auto f = [](P l, P r) {
      l.first = min(l.first, r.first);
      l.second = min(l.second, r.second);
      return l;
    };
    auto g = [](P l, dat r) {
      r.p.first += l.second - r.p.second;
      r.p.first = min(r.p.first, inf);
      r.p.second = l.second;
      if (r.re) return r.p;
      return min(l, r.p);
    };
    auto h = [](dat l, dat r) {
      if (r.re) return r;
      if (l.p.second > r.p.second) swap(l.p, r.p);
      l.p.first += r.p.second - l.p.second;
      l.p.second = r.p.second;
      l.p = min(l.p, r.p);
      l.p.first = min(l.p.first, inf);
      return l;
    };
    seg1 = SegmentTreeLaze<P, dat>(tmp, f, g, h, P(inf, inf), dat());
  }
  {
    vector<P> tmp(w);
    for (int i = 0; i < w; ++i) {
      if (v[0].first <= i && i < v[0].second)
        tmp[i].first = inf;
      else
        tmp[i].first = -i;
      tmp[i].second = i;
    }
    auto f = [](P l, P r) { return min(l, r); };
    auto g = [](P l, dat r) {
      if (r.re) return r.p;
      return min(l, r.p);
    };
    auto h = [](dat l, dat r) {
      if (r.re) return r;
      l.p = min(l.p, r.p);
      return l;
    };
    seg2 = SegmentTreeLaze<P, dat>(tmp, f, g, h, P(inf, inf), dat());
  }
  for (int i = 1; i <= h; ++i) {
    long long res = min(seg1.query(0, w).first, inf);
    if (res == inf)
      cout << -1 << endl;
    else
      cout << res + i << endl;
    {
      P now = seg2.query(0, v[i - 1].first);
      if (now.first != inf) {
        now.first += now.second;
        seg1.update(v[i - 1].first, w, dat(0, now));
        now.first -= now.second;
        seg2.update(v[i - 1].first, w, dat(0, now));
      }
    }
    seg2.update(v[i].first, v[i].second, dat(1));
    seg1.update(v[i].first, v[i].second, dat(1));
  }
  return 0;
}

Measured memory_bytes: 26732