#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;
//const i64 inf = 1'000'000'000'000'000'000ll + 7;
//const i64 inf = 1'000'000'007;

const i64 inf = mod;

const long double eps = 1e-8;

i64 rows, cols;
vector<pair<i64, i64>> lims;

struct TNode {
    i64 x;
    i64 y;
    i64 i;
};

struct less_key {
    bool operator() (const TNode& p1, const TNode& p2)  const {
        return make_tuple(p1.x, p1.y, p1.i) < make_tuple(p2.x, p2.y, p2.i);
    }
};


int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed); cerr.precision(15); cerr.setf(ios::fixed);

    cin >> rows >> cols;
    lims = vector<pair<i64, i64>>(rows + 2);
    for (i64 i = 1; i <= rows; i++) {
        cin >> lims[i].first >> lims[i].second;
    }
    lims[rows + 1] = { 1, cols };

    set<i64> active;
    set<TNode, less_key> scanline;
    for (i64 i = 1; i <= rows + 1; i++) {
        scanline.insert({ lims[i].first, 0, i });
        scanline.insert({ lims[i].second + 1, 0, i });
    }

    for (i64 i = 1; i <= cols; i++) {
        if (i < lims[1].first || i > lims[1].second) {
            scanline.insert({ i, 1, 0 });
        }
    }

    for (i64 i = 1; i <= rows; i++) {
        if (lims[i].second < cols) {
            scanline.insert({ lims[i].second + 1, i, 0 });
        }
    }

    map<pair<i64, i64>, i64> hits;

    for (auto t : scanline) {
        if (t.i) {
            if (active.count(t.i)) {
                active.erase(t.i);
            }
            else {
                active.insert(t.i);
            }
            continue;
        }

        if (t.x <= cols) {
            hits[{t.y, t.x}] = *active.lower_bound(t.y) - t.y;
        }
    }

    map<pair<i64, i64>, i64> cost;
    for (auto t : hits) {
        i64 y = t.first.first;
        i64 x = t.first.second;
        i64 h = t.second;

        if (y == 1) {
            cost[{y, x}] = 0;
        }

        if (!cost.count({ y, x })) {
            continue;
        }

        i64 ny = y + h;
        i64 nx = lims[ny].second + 1;
        if (nx > cols) {
            continue;
        }
        //i64 nc = h + nx - x + cost[{y, x}];
        i64 nc = nx - x + cost[{y, x}];
        if (!cost.count({ ny, nx }) || cost[{ny, nx}] > nc) {
            cost[{ny, nx}] = nc;
        }
    }

    set<pair<i64, pair<i64, i64>>> q;
    for (auto t : cost) {
        i64 y = t.first.first;
        i64 x = t.first.second;
        i64 c = t.second;

        q.insert({ y, {y, x} });
        q.insert({ y + hits[{y, x}], {y, x} });
    }

    for (i64 i = 1; i <= rows; i++) {
        q.insert({ i, {inf, inf} });
    }

    set<pair<i64, i64>> pactive;
    set<pair<i64, pair<i64, i64>>> pairline;

    vector<i64> ans(rows + 1, -1);

    for (auto t : q) {
        i64 cy = t.first;
        i64 y = t.second.first;
        i64 x = t.second.second;

        if (y == inf) {
            if (!pairline.empty()) {
                ans[cy] = pairline.begin()->first + cy;
            }
            continue;
        }
        if (pactive.count({ y, x })) {
            pactive.erase({ y, x });
            pairline.erase({ cost[{y, x}], {y, x} });
        }
        else {
            pactive.insert({ y, x });
            pairline.insert({ cost[{y, x}],{ y, x } });
        }
    }

    stringstream ss;
    for (i64 i = 1; i <= rows; i++) {
        ss << ans[i] << endl;
    }
    cout << ss.str();
    return 0;
}

Measured memory_bytes: 195284