#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

int H, W;
const int INF = 1e9;
struct LazySegmentTree
{
private:
    int n;
    vector<int> node, lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree(vector<int> v)
    {
        int sz = (int)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, INF);
        lazyFlag.resize(2 * n - 1, false);

        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
    }

    void lazyEvaluate(int k, int l, int r)
    {
        if (lazyFlag[k])
        {
            node[k] = lazy[k];
            if (r - l > 1)
            {
                lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
                lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] = x;
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else
        {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    int find(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return INF;
        if (a <= l && r <= b)
            return node[k];
        int vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};
struct LazySegmentTree2
{
private:
    int n;
    vector<pair<int, int>> node;
    vector<int> lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree2(vector<pair<int, int>> v)
    {
        int sz = (int)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, INF);
        lazyFlag.resize(2 * n - 1, false);

        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            if (node[i * 2 + 1].first + node[i * 2 + 1].second < node[i * 2 + 2].first + node[i * 2 + 2].second)
                node[i] = node[i * 2 + 1];
            else
                node[i] = node[i * 2 + 2];
    }

    void lazyEvaluate(int k, int l, int r)
    {
        if (lazyFlag[k])
        {
            node[k] = make_pair(lazy[k], -r + 1);
            if (r - l > 1)
            {
                lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
                lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] = x;
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else
        {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (node[k * 2 + 1].first + node[k * 2 + 1].second < node[k * 2 + 2].first + node[k * 2 + 2].second)
                node[k] = node[k * 2 + 1];
            else
                node[k] = node[k * 2 + 2];
        }
    }

    int find(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return INF;
        if (a <= l && r <= b)
            return node[k].first + node[k].second;
        int vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};
int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    cin >> H >> W;
    auto segt = LazySegmentTree(vector<int>(W + 10));
    vector<pair<int, int>> _p(W + 10);
    REP(i, 0, W + 10)
    _p[i] = make_pair(0, -i);
    auto segt2 = LazySegmentTree2(_p);

    int l, r;
    int ng = INF >> 1;
    REP(i, 1, H + 1)
    {
        cin >> l >> r;
        ++r;
        int x = segt2.find(l, r) + r;
        segt.update(l, r, INF);
        segt2.update(l, r, INF);
        int y = min(segt.find(r, r + 1), x);
        segt.update(r, r + 1, y);
        segt2.update(r, r + 1, y);
        int res = min(segt.find(1, l), segt.find(r, W + 1));
        cout << (res < ng ? res + i : -1) << "\n";
    }
}

Measured memory_bytes: 16776