#include <bits/stdc++.h>

using namespace std;

template <ranges::range T,
          class = enable_if_t<!is_convertible_v<T, string_view>>>
istream &operator>>(istream &s, T &&v) {
    for (auto &&x : v)
        s >> x;
    return s;
}
template <ranges::range T,
          class = enable_if_t<!is_convertible_v<T, string_view>>>
ostream &operator<<(ostream &s, T &&v) {
    for (auto &&x : v)
        s << x << ' ';
    return s;
}

#ifdef LOCAL
template <class... T> void dbg(T... x) {
    char e{};
    ((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

template <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
template <class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template <class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 mod = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> seg(n);
    for (auto &[l, r] : seg) {
        cin >> l >> r;
    }

    vector<int> ans(n);
    vector<int> ord(n);
    iota(all(ord), 0);
    
    sort(all(ord), [&](int a, int b) {
            return seg[a] < seg[b];
        });

    int cur = -1;
    int cnt = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int ti = 0;
    for (int r = 0; r < n;) {
        while(pq.empty() && seg[ord[r]].ff > ti) ++ti;
        while(r < n && seg[ord[r]].ff <= ti){
            pq.push(make_pair(seg[ord[r]].ss, ord[r]));
            ++r;
        }
        for(int j = 0; j < k && !pq.empty(); j++){
            ans[pq.top().second] = ti;
            pq.pop();
        }
        ++ti;
    }
    while(!pq.empty()){
        for(int i = 0; i < k && !pq.empty(); i++){
            ans[pq.top().second] = ti;
            pq.pop();
        }
        ++ti;
    }

    for (int x : ans) {
        cout << x << '\n';
    }
    
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}