// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 5;
const int LG = 20;
int N, K;
void Solve(void) {
  cin >> N >> K;
  vector<int> l(N), r(N), ans(N);
  vector<vector<pair<int, int>>> st(33);
  for (int i = 0; i < N; i ++) {
    cin >> l[i] >> r[i];
    st[l[i]].pb(mp(r[i], i));
  }
  vector<pair<int, int>> cur;
  for (int d = 1; d <= 31; d ++) {
    for (auto [y, id] : st[d]) {
      cur.pb(mp(y, id));
    }
    sort(cur.rbegin(), cur.rend());
    int cnt = K;
    while (!cur.empty() && cnt > 0) {
      cnt --;
      ans[cur.back().second] = d;
      cur.pop_back();
    }
  }
  for (int i = 0; i < N; i ++) cout << ans[i] << "\n";

}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}