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

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define b_e(a) a.begin(),a.end() //sort(b_e(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define p_b push_back
#define SZ(x) ((ll)(x).size()) //size()がunsignedなのでエラー避けに
#define endk '\n'


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //




// --------- library end - //


int main(){

  ll H, W;
  cin >> H >> W;
  
  // 現在見ている行に辿り着くときの <終点列の列番号, その列に行き着く始点列> の set
  // ただし、不要な行は削除する
  // 不要な行 : 例えば、ある行の処理をしたときに「2, 3, 4行目からスタートすると、それぞれ 4, 4, 4 行目 に辿り着く」という状態になった時、その行から先を考える限りにおいては、2, 3行目からスタートするメリットは無い。このように「終点列が一致してしまったペアのうち、もっとも始点列の列番号が大きいペア」以外を削除する
  set<pair<ll, ll> > goal_and_starts;

  // goal_and_starts に格納されている各ペアの .first - .second を格納
  // つまり 終点列 - 始点列 だから、「何回右に移動する必要があるか」を意味する
  // これの最小値 + k が、k 行における答えとなる
  // goal_and_starts でペアを削除(更新)するとき、ここの対応する値も削除(更新)する
  multiset<ll> moves;

  // 注) r が W-1 であった場合、つまり盤の外側に押し出されてしまう（下の行に行けない）場合、解説では無限にするとあったが、この実装では、削除してしまうことにした

  
  // k=0 つまり開始前においては、終点行 = 始点行
  // moves の内容は、全て 0
  rep(w, W){
    goal_and_starts.insert(m_p(w, w));
    moves.insert(0);
  }

  // 各 k について set, multiset を管理しながら答えを出していく
  // O(H*W) になりそうだが、区間が与えられる度に set の中身が減っていくので、解説のとおり計算量は大きくない

  bool cannotreach = false; // それ以降の行に辿り着けなくなったらこのフラグを立てる
  REP(k, 1, H+1){
    // k : 1 ~ H
    ll l = il() - 1;
    ll r = il() - 1; // 0-indexed

    if (cannotreach){
      cout << -1 << endk;
      continue;
    }

    // k-1 行で l 列目に辿り着くような始点列は、k 行で全て r+1 列目に辿り着いてしまう
    // よって、現時点で goal_and_starts に入っているペアのうち、.first が l ~ r のペアは、最も後ろにある（最も始点列の列番号が大きい＝右移動が少なくて済む）ものだけ残し、削除する
    // l_it := [l, r] に辿り着くペアのうち、最も始点列が左側のもの（のイテレータ）
    // r_it := [l, r] に辿り着くペアのうち、最も始点列が右側のもの の直後を指す
    auto l_it = goal_and_starts.lower_bound(m_p(l, 0));
    auto r_it = goal_and_starts.lower_bound(m_p(r+1, 0));
    if (l_it == r_it){
      // 一つも条件を満たすペアが無い時（終点列の列番号が「全て l 未満」か「全て r+1 以上」）
      // この行の入力は何も影響を及ぼさないということなので、set, multiset に対する処理は何もしない
    }
    else{
      // [l, r] に辿り着くペアのうち、最も始点列が右側のもの「の直後」を指していたイテレータを、1つ前に戻す。これで [l, r] に辿り着くペアのうち最も始点列が右側のものを指すようになる
      r_it--;

      // ペア [l_it, r_it) を削除する
      // ここですぐに set を操作し始めると添字が変わってしまうため、削除したいペアをリストアップ
      vector<pair<ll, ll> > pairs_toerase;
      vector<ll> moves_toerase;
      while(l_it != r_it){
        pairs_toerase.push_back(*l_it);
        moves_toerase.push_back((*l_it).first - (*l_it).second);

        l_it++;
      }

      // k行目において r にいたペアは、k-1行目において r+1 にいくことになるから、更新したペアを入れ直したあと、削除する
      // r == W-1 の場合は、k-1行目において [l, r] にいるとそもそも下の行に辿り着けないので、入れ直しはせず、ただ削除するだけ
      pairs_toerase.push_back(*r_it);
      moves_toerase.push_back((*r_it).first - (*r_it).second);
      if (r != W-1){
        goal_and_starts.insert(m_p(r + 1, (*r_it).second) );
        moves.insert((r + 1 - (*r_it).second));
      }
      
      // 削除の処理を行う
      rep(i, SZ(pairs_toerase)){
        goal_and_starts.erase(pairs_toerase[i]);

        // multiset は普通に .erase(key) をかけると重複する値も全部消してしまうので、イテレータを使う
        auto it = moves.find(moves_toerase[i]);
        if (it != moves.end()) {
            moves.erase(it);
        }
      }
    }

    // これで、moves 内の最小値 + k が k 行における答えとなる
    // ただし、set に要素が1つもなくなっていた場合、その行には到達不可能なので、残り全てで -1 を出力する
    if (moves.size() == 0){
      cannotreach = true;
      cout << -1 << endk;
    }
    else{
      cout << *(moves.begin()) + k << endk;
    }
  }


}

Measured memory_bytes: 25636