#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int n, m, ans[N]; pair<int, int> A[N];
vector<int> vec[N], lsh;
vector<int> C[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        int l, r; cin >> l >> r;
        A[i] = {l, r};
        lsh.emplace_back(l), lsh.emplace_back(r);
    }
    sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    for(int i = 1; i <= n; i ++) {
        A[i].first = lower_bound(lsh.begin(), lsh.end(), A[i].first) - lsh.begin() + 1;
        A[i].second = lower_bound(lsh.begin(), lsh.end(), A[i].second) - lsh.begin() + 1;
        vec[A[i].first].emplace_back(i);
    }

    vector<int> single;
    int tot = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
    for(int i = 1; i <= 2 * n; i ++) {
        for(auto id : vec[i]) {
            int r = A[id].second;
            if(!single.empty()) {
                int u = single.back(); single.pop_back();
                ans[u] = ++tot; ans[id] = ans[u];
                Q.push({r, id});
            } else if(!Q.empty() && Q.top().second < r) {
                int u = Q.top().first; Q.pop();
                swap(ans[u], ans[id]); Q.push({id, r});
                if(A[u].second < i) single.emplace_back(u);
                else C[A[u].second].emplace_back(u);
            } else C[r].emplace_back(id);
        }
        while(!C[i].empty()) single.emplace_back(C[i].back()), C[i].pop_back();
    }
    while(tot < m && !single.empty()) ans[single.back()] = ++tot, single.pop_back();
    for(int i = 1; i <= n; i ++)
        if(ans[i] <= m) cout << ans[i] << ' ';
        else cout << "0" << ' ';
    cout << '\n';

    return 0;
}