#include <bits/stdc++.h>
using namespace std;
const long long N = 111111;
pair<long long, long long> stud[N];
long long ttoi[N], ans[N];
set<long long> off[N];
long long n, m;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (long long i = (1); i <= (n); i++) {
    long long t, x;
    cin >> t >> x;
    stud[i] = {t, x};
    ttoi[t] = i;
  }
  vector<pair<long long, long long> > bus;
  long long t = 0;
  for (long long i = (1); i <= (n); i++) {
    bus.push_back({stud[i].second, stud[i].first});
    t = max(t, stud[i].first);
    if (i % m == 0 || i == n) {
      set<long long> post;
      for (auto p : bus) {
        off[p.first].insert(ttoi[p.second]);
        post.insert(p.first);
      }
      long long cx = 0;
      for (auto x : post) {
        t += x - cx;
        for (auto id : off[x]) {
          ans[id] = t;
        }
        t += 1 + (long long)(off[x]).size() / 2;
        cx = x;
        off[x].clear();
      }
      t += cx;
      bus.clear();
    }
  }
  for (long long i = (1); i <= (n); i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
  return 0;
}
