#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

pii arr[300005];
int ans[300005], idx[300005], mch[300005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int tp = 0;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i].X >> arr[i].Y;
    iota(idx + 1, idx + n + 1, 1);
    sort(idx + 1, idx + n + 1, [&](int a, int b) {
        if (arr[a].Y != arr[b].Y) return arr[a].Y < arr[b].Y;
        return arr[a].X < arr[b].X;
    });
    set<pii> st, st2;
    for (int i = 1; i <= n; ++i) {
        int u = idx[i];
        auto p = st.lower_bound(pii(arr[u].X, 0));
        if (p != st.begin()) {
            --p;
            if (tp < m) {
                ++tp;
                ans[p->Y] = tp;
                ans[u] = tp;
            }
            mch[u] = p->Y;
            st.erase(p), st2.insert(pii(arr[u].Y, u));
        }
        else {
            p = st2.lower_bound(pii(arr[u].X, 0));
            if (p != st2.begin()) {
                --p;
                ans[u] = ans[p->Y];
                ans[mch[p->Y]] = 0;
                mch[u] = p->Y;
                st.insert(pii(arr[mch[p->Y]].Y, mch[p->Y])), st2.erase(p);
            }
            else
                st.insert(pii(arr[u].Y, u));
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!ans[i] && tp < m) ans[i] = ++tp;
        cout << ans[i] << " \n"[i == n];
    }
}