#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct unit {
  int x, t;
  int ind;
};
unit a[N], b[N];
int n, m, p, len, t, pos;
int ans[N];
bool cmpx(unit a, unit b) { return a.x < b.x; }
bool cmpt(unit a, unit b) { return a.t < b.t; }
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a[i].t, &a[i].x);
    a[i].ind = i;
  }
  sort(a, a + n, cmpt);
  for (int i = 0; i < n;) {
    len = pos = 0;
    for (int j = i; j < min(n, i + m); j++) b[len++] = a[j];
    t = max(t, b[len - 1].t);
    sort(b, b + len, cmpx);
    for (int j = 0; j < len;) {
      int r = j + 1;
      while (r < len && b[r].x == b[j].x) r++;
      t += b[j].x - pos;
      pos = b[j].x;
      for (int q = j; q < r; q++) ans[b[q].ind] = t;
      t += 1 + (r - j) / 2;
      j = r;
    }
    i += len;
    t += pos;
  }
  for (int i = 0; i < n; i++) printf("%d ", ans[i]);
  return 0;
}
