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

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ll> llll;
typedef pair<double, double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a) int((a).size())
#define pb push_back
#define eb emplace_back
#define FOR(var, from, to) for (int var = (from); var <= (to); ++var)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define rep1(var, n) for (int var = 1; var <= (n); ++var)
#define repC2(vari, varj, n)                 \
    for (int vari = 0; vari < (n)-1; ++vari) \
        for (int varj = vari + 1; varj < (n); ++varj)
#define repC3(vari, varj, vark, n)                      \
    for (int vari = 0; vari < (n)-2; ++vari)            \
        for (int varj = vari + 1; varj < (n)-1; ++varj) \
            for (int vark = varj + 1; vark < (n); ++vark)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define tr(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define found(s, e) ((s).find(e) != (s).end())
#define mset(arr, val) memset(arr, val, sizeof(arr))
#define mid(x, y) ((x) + ((y) - (x)) / 2)
#define IN(x, a, b) ((a) <= (x) && (x) <= (b))
#define cons make_pair
#define clamp(v, lo, hi) min(max(v, lo), hi)
#define ABS(x) max((x), -(x))
#define PQ(T) priority_queue<T, vector<T>, greater<T>>

template <typename T1, typename T2>
inline void amin(T1& a, T2 const& b) {
    if (a > b) a = b;
}
template <typename T1, typename T2>
inline void amax(T1& a, T2 const& b) {
    if (a < b) a = b;
}
template <typename X, typename T>
auto vectors(X x, T a) {
    return vector<T>(x, a);
}
template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
    auto cont = vectors(y, z, zs...);
    return vector<decltype(cont)>(x, cont);
}

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) {
    while (a) swap(a, b %= a);
    return b;
}
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template <typename T>
inline T mod(T a, T b) {
    return ((a % b) + b) % b;
}

template <typename T>
int find_left(vector<T>& v, T elem) {
    return (int)(upper_bound(v.begin(), v.end(), elem) - v.begin()) - 1;
}
template <typename T>
int find_right(vector<T>& v, T elem) {
    return (int)(lower_bound(v.begin(), v.end(), elem) - v.begin());
}

typedef enum { MINIMUM, MAXIMUM } MinMax;

template <typename T>
class SegmentTree {
   public:
    int bit_, N;
    vector<T> buf_;
    T invalid;
    MinMax mode;

    SegmentTree(int size, MinMax mode = MINIMUM) : mode(mode) {
        N = 1;
        bit_ = 0;
        while (N < size) {
            N *= 2;
            ++bit_;
        }

        switch (mode) {
            case MINIMUM:
                if (sizeof(T) == 4) {
                    invalid = INT_MAX;
                } else if (sizeof(T) == 8) {
                    invalid = LLONG_MAX;
                }
                break;
            case MAXIMUM:
                if (sizeof(T) == 4) {
                    invalid = INT_MIN;
                } else if (sizeof(T) == 8) {
                    invalid = LLONG_MIN;
                }
                break;
        }
        buf_.assign(N * 2, invalid);
    }

    T merge(T l, T r) {
        switch (mode) {
            case MINIMUM:
                return min(l, r);
            case MAXIMUM:
                return max(l, r);
        }
    }

    void update(int i, T x) {
        i = N + i - 1;


        buf_[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            buf_[i] = merge(buf_[i * 2 + 1], buf_[i * 2 + 2]);
        }
    }

    T query(int lo, int hi) {
        return query(lo, hi, 0, 0, N);
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return invalid;

        if (a <= l && r <= b) {
            return buf_[k];
        } else {
            T lv = query(a, b, 2 * k + 1, l, (l + r) / 2);
            T rb = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return merge(lv, rb);
        }
    }

    void dump() {
    }
};

void solve(int H, int W, vi& a, vi& b) {
    using P = tuple<int, int, int, int>;
    set<P> s;
    s.insert({0, W, 0, 0});
    s.insert({INT_MIN, 0, INT_MAX, 0});
    s.insert({W, INT_MAX, INT_MAX, 0});


    SegmentTree<int> seg(W + 1, MINIMUM);
    seg.update(0, 0);

    rep(i, H + 1) {
        if (i > 0) {
            int minimum = seg.query(0, W);
            if (minimum > W) {
                printf("-1\n");
                s.clear();
                s.insert({0, W, INT_MAX, 0});
                s.insert({INT_MIN, 0, INT_MAX, 0});
                s.insert({W, INT_MAX, INT_MAX, 0});
                continue;
            }
            printf("%d\n", i + minimum);
            if (i == H) break;
        }

        auto it = s.lower_bound({a[i] - 1, INT_MAX, 1, 1});
        {
            int ilo = get<0>(*it);
            if (a[i] - 1 < ilo) --it;
        }

        auto jt = s.lower_bound({b[i], INT_MAX, INT_MAX, 1});
        {
            int jlo = get<0>(*jt);
            if (b[i] < jlo) --jt;
        }
        auto [ilo, ihi, icost, islant] = *it;
        auto [jlo, jhi, jcost, jslant] = *jt;

        assert(IN(a[i] - 1, ilo, ihi - 1));
        assert(IN(b[i], jlo, jhi - 1));

        vector<P> to_erase, to_insert;
        ++jt;
        for (auto at = it; at != jt; ++at) {
            auto [lo, hi, cost, slant] = *at;
            if (lo == INT_MIN) continue;

            seg.update(lo, INT_MAX);
            to_erase.pb(*at);
        }
        --jt;

        if (ilo != INT_MIN && ilo < a[i]) {
            to_insert.eb(ilo, a[i], icost, islant);
            seg.update(ilo, icost);
        }

        if (ilo != INT_MIN && icost <= W) {
            int w = islant ? a[i] - ilo : 1;
            to_insert.eb(a[i], b[i] + 1, icost + w, 1);
            seg.update(a[i], icost + w);
        } else {
            to_insert.eb(a[i], b[i] + 1, INT_MAX, 0);
            seg.update(a[i], INT_MAX);
        }

        if (b[i] + 1 < jhi && jcost <= W) {
            int w = jslant ? (b[i] + 1 - jlo) : 0;
            to_insert.eb(b[i] + 1, jhi, jcost + w, jslant);
            seg.update(b[i] + 1, jcost + w);
        }

        for (const P& p : to_erase) {
            s.erase(p);
        }
        for (const P& p : to_insert) {
            s.insert(p);
        }
    }
}

int main() {
    int H, W;
    scanf("%d %d%*c", &H, &W);
    vi a(H), b(H);
    rep(i, H) {
        scanf("%d %d%*c", &a[i], &b[i]);
        --a[i];
        --b[i];
    }

    solve(H, W, a, b);

    return 0;
}


Measured memory_bytes: 19388