#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Node {
    int x, y;
    int siz = 0;
    Node* l, * r;
    Node(int _x) : x(_x) {
        y = rnd();
        siz = 1;
        l = nullptr;
        r = nullptr;
    }
};
int siz(Node* t) {
    if (t == nullptr) {
        return 0;
    }
    return t->siz;
}
int calc(Node* a) {
    int res = 0;
    if (a == nullptr)return res;
    if (a->l != nullptr) {
        res += (a->l)->siz;
    }
    if (a->r != nullptr) {
        res += (a->r)->siz;
    }
    return res;
}
void upd(Node* a) {
    if (a == nullptr)return;
    a->siz = 1;
    a->siz += calc(a);
}
typedef pair<Node*, Node*> Tree;

Tree split(Node* a, int x) {
    if (a == nullptr) return { nullptr, nullptr };
    if (a->x < x) {
        Tree p = split(a->r, x);
        a->r = p.first;
        upd(a);
        return { a, p.second };
    }
    else {
        Tree p = split(a->l, x);
        a->l = p.second;
        upd(a);
        return { p.first,a };
    }
}

Node* merge(Node* a, Node* b) {
    if (a == nullptr)return b;
    if (b == nullptr)return a;
    if (a->y > b->y) {
        a->r = merge(a->r, b);
        upd(a);
        return a;
    }
    else {
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

Node* insert(Node* a, Node* x) {
    if (!a) return x;
    if (!x) return a;
    if (x->y > a->y) {
        Tree p = split(a, x->x);
        x->l = p.first;
        x->r = p.second;
        upd(x);
        return x;
    }
    if (x->x < a->x) {
        a->l = insert(a->l, x);
        upd(a);
        return a;
    }
    else {
        a->r = insert(a->r, x);
        upd(a);
        return a;
    }
}

Node* erase(Node* a, int x) {
    if (a == nullptr)return nullptr;
    Tree p1 = split(a, x);
    Tree p2 = split(p1.second, x + 1);
    return merge(p1.first, p2.second);
}
int get_k_stat(Node* a, int k) {
    int res_r = 0;
    if (a->r != nullptr) {
        res_r += (a->r)->siz;
    }
    if (k == res_r + 1) {
        return a->x;
    }
    else if (res_r + 1 > k) return get_k_stat(a->r, k);
    else return get_k_stat(a->l, k - res_r - 1);
}

signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    if(m <= 1e6 + 1) {
        Node* T = nullptr;
        for (int i = 1; i <= m; i++) {
            T = insert(T, new Node(i));
        }
        for (int i = 0; i < n; i++) {
            int l, r; cin >> l >> r;
            l--, r--;
            vector<int> del;
            int sz = siz(T);
            for (int j = l; j <= r; j += 2) {
                del.push_back(get_k_stat(T, sz - j));
            }
            cout << del[0] << ' ' << del.back() << '\n';
            for (int& i : del) {
                T = erase(T, i);
            }
        }
    }
    else if (n <= 10000) {
        vector<pair<int, int>> a;
        auto rotate = [&](int pref) {
            for (int i = (int)a.size() - 1; i >= 0; i--) {
                if (pref < a[i].first) {
                    continue;
                }
                pref += min((a[i].second - a[i].first) / 2, pref - a[i].first) + 1;
            }
            return pref;
        };
        for (int i = 0; i < n; i++) {
            int l, r; cin >> l >> r;
            cout << rotate(l) << ' ' << rotate(r) << '\n';
            a.push_back({l, r});
        }
    }
    else {
        return 132;
    }
}