#include <bits/stdc++.h>
using namespace std;
struct stud {
  long long t, x, ans, num;
};
bool ls(stud a, stud b) { return a.t < b.t; }
bool ls2(stud a, stud b) { return a.x < b.x; }
bool ls3(stud a, stud b) { return a.num < b.num; }
int main() {
  int n, m;
  cin >> n >> m;
  vector<stud> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].t >> a[i].x;
    a[i].num = i;
  }
  sort(a.begin(), a.end(), ls);
  long long cur = 0;
  for (int i = 0; i < n; i += m) {
    int fst = i, lst = min(i + m, n);
    cur = max(cur, a[lst - 1].t);
    sort(a.begin() + fst, a.begin() + lst, ls2);
    int curx = 0;
    for (int j = fst; j < lst;) {
      int k;
      for (k = j; k < lst && a[j].x == a[k].x; ++k)
        ;
      cur += a[j].x - curx;
      curx = a[j].x;
      for (int l = j; l < k; ++l) {
        a[l].ans = cur;
      }
      cur += 1 + (k - j) / 2;
      j = k;
    }
    cur += curx;
  }
  sort(a.begin(), a.end(), ls3);
  for (int i = 0; i < n; ++i) cout << a[i].ans << ' ';
  return 0;
}
