#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
#define x first
#define y second
#define int long long
#define double long double
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define beg begin
#define dbg(x) cerr << #x << " = " << x << endl;
 
template<class T> ostream& operator<<(ostream &str, vector<T> &a) {
    for (auto &i : a) {
        str << i << " ";
    }
    return str;
}
 
template<class T> istream& operator>>(istream &str, vector<T> &a) {
    for (auto &i : a) {
        str >> i;
    }
    return str;
}
 
template<class T> ostream& operator<<(ostream &str, pair<T, T> &a) {
    str << a.first << " " << a.second;
    return str;
}
 
template<class T> istream& operator>>(istream &str, pair<T, T> &a) {
    str >> a.first >> a.second;
    return str;
}
 
void solve(); signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20);
    solve();
    return 0;
}

const int MAXN = 1e6 + 10, INF = 1e18 + 10;
int H, W;
vec<pii> sg;

void solve() {
    cin >> H >> W;
    sg.resize(H);
    cin >> sg;
    set<vec<int>> se, mn;
    for (int i = 1; i <= W; ++i) {
        se.insert({i, i, 0});
        mn.insert({0, i, i});
    }

    for (int h = 1; h <= H; ++h) {
        int l = sg[h - 1].x, r = sg[h - 1].y;
        vec<vec<int>> tmp;
        if (se.lower_bound({l, 0, 0}) != se.end()) {
            for (auto it = se.lower_bound({l, 0, 0}); it != se.end() && (*it)[1] <= r; ++it) {
                auto cur = *it;
                tmp.pb(cur);
            }
            for (auto cur : tmp) {
                se.erase(cur);
                mn.erase({cur[2], cur[0], cur[1]});
            }    
        }
        
        auto cur = se.lower_bound({l, 0, 0});
        if (cur != se.end()) {
            auto it = *cur;
            if (it[0] <= r) {
                se.erase(it);
                mn.erase({it[2], it[0], it[1]});
                it[2] += (r - it[0] + 1);
                it[0] = r + 1;
                if (it[0] <= it[1]) {
                    se.insert(it);
                    mn.insert({it[2], it[0], it[1]});
                }
            }
        }
        if (l == 1) {
            se.insert({l, r, INF});
            mn.insert({INF, l, r});
        }
        else {
            auto cur = se.lower_bound({l, 0, 0});
            if (cur == se.begin()) {
                se.insert({l, r, 1});
                mn.insert({1, l, r});
            }
            else {
                --cur;
                auto it = *cur;
                if (it[1] < l) {
                    int first = it[2] + 1 + it[1] - it[0];
                    se.insert({l, r, first});
                    mn.insert({first, l, r});
                }
                else {
                    if (it[1] <= r) {
                        int first = (l - it[0]) + it[2];
                        se.erase(it);
                        mn.erase({it[2], it[0], it[1]});
                        se.insert({l, r, first});
                        mn.insert({first, l, r});
                        se.insert({it[0], l - 1, it[2]});
                        mn.insert({it[2], it[0], l - 1});    
                    }
                    else {
                        int first = (l - it[0]) + it[2] + 1;
                        int second = (r - it[0]) + it[2] + 1;
                        se.erase(it);
                        mn.erase({it[2], it[0], it[1]});
                        se.insert({l, r, first});
                        mn.insert({first, l, r});
                        se.insert({it[0], l - 1, it[2]});
                        mn.insert({it[2], it[0], l - 1}); 
                        se.insert({r + 1, it[1], second});
                        mn.insert({second, r + 1, it[1]});
                    }
                }
            }
        }

        int ans = h + (*mn.begin())[0];
        if (ans < INF / 2) {
            cout << ans << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
}

Measured memory_bytes: 44196