#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <unordered_map>

using namespace std;

using ll = long long;
// const int mod = 1e9 + 7;

#define mem(a, b) memset(a, b, sizeof(a))
#define REP(i, a) for (int i = 0; i < a; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(a) a.begin(), a.end()

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(10);
}

inline void print_vector(vector<ll> &A){
    for (auto&& x : A){
        cout << x << " ";
    }
    cout << endl;
}

inline void print_array(const int A[], int n) {
    REP(i, n) {
        if (i < n - 1) {
            cout << A[i] << " ";
        } else {
            cout << A[i] << endl;
        }
    }
}


#define lson (idx << 1)
#define rson (idx << 1 | 1)
#define INF 1000000000000LL
#define MAXN 200010

struct Node {
  int l, r;
  ll lo, lh, lazy = 0;
  bool flag = false;
} s[MAXN << 2];

int h, w;

void calc(int idx) {
  s[idx].lo = min(s[lson].lo, s[rson].lo);
  s[idx].lh = s[lson].lh;
}

void build(int idx, int l, int r) {
  s[idx].l = l, s[idx].r = r;
  if (l == r)
    return;
  int mid = (l + r) >> 1;
  build(lson, l, mid);
  build(rson, mid + 1, r);
}

// Lazy propagation
void pushdown(int idx) {
  if (s[idx].flag) {
    ll L = s[idx].lh;
    int l = s[idx].l;
    for (int i = lson; i <= rson; ++i) {
      s[i].lo = s[i].lh = L + s[i].l - l;
      s[i].flag = true;
      s[i].lazy = 0;
    }
  } else if (s[idx].lazy) {
    for (int i = lson; i <= rson; ++i) {
      s[i].lh += s[idx].lazy;
      s[i].lo += s[idx].lazy;
      s[i].lazy += s[idx].lazy;
    }
  }
  s[idx].flag = false;
  s[idx].lazy = 0;
}

// Assign segment [l, r] according to f[l-1] = L
void update(int idx, int l, int r, ll L) {
  if (s[idx].l >= l && s[idx].r <= r) {
    s[idx].lo = s[idx].lh = L + s[idx].l - l + 1;
    s[idx].flag = true;
    s[idx].lazy = 0;
    return;
  }
  pushdown(idx);
  int mid = (s[idx].l + s[idx].r) >> 1;
  if (l <= mid)
    update(lson, l, r, L);
  if (mid + 1 <= r)
    update(rson, l, r, L);
  calc(idx);
}

// Range addition
void add(int idx, int l, int r) {
  if (s[idx].l >= l && s[idx].r <= r) {
    s[idx].lh++;
    s[idx].lo++;
    s[idx].lazy++;
    return;
  }
  pushdown(idx);
  int mid = (s[idx].l + s[idx].r) >> 1;
  if (l <= mid)
    add(lson, l, r);
  if (mid + 1 <= r)
    add(rson, l, r);
  calc(idx);
}

// Range minimum query
ll query(int idx, int l, int r) {
  if (r < 1 || l > w)
    return INF;
  if (s[idx].l >= l && s[idx].r <= r)
    return s[idx].lo;
  pushdown(idx);
  ll ans = INF;
  int mid = (s[idx].l + s[idx].r) >> 1;
  if (l <= mid)
    ans = min(ans, query(lson, l, r));
  if (mid + 1 <= r)
    ans = min(ans, query(rson, l, r));
  return ans;
}

inline void solve() {
    cin >> h >> w;

    vector<int> l(h), r(h);

    for (int i = 0; i < h; ++i) {
        cin >> l[i] >> r[i];
    }

    vector<ll> ans(h, INF);

    build(1, 1, w);
    for (int i = 0; i < h; ++i) {
      if (l[i] > 1)
        add(1, 1, l[i] - 1);
      if (r[i] < w)
        add(1, r[i] + 1, w);
      ll L = query(1, l[i] - 1, l[i] - 1);
      update(1, l[i], r[i], L);
      ans[i] = min(ans[i], query(1, 1, w));
      if (ans[i] == INF)
        break;
    }
    for (ll i : ans)
      cout << (i == INF ? -1 : i) << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    int t = 1;
    // cin >> t;

    for (int _ = 0; _ < t; _++) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 37500