#include <bits/stdc++.h>
class xt {
 public:
  int x;
  int t;
  int i;
};
int sx(const void* a, const void* b) { return (*(xt*)a).x - (*(xt*)b).x; }
int st(const void* a, const void* b) { return (*(xt*)a).t - (*(xt*)b).t; }
int main() {
  int n, m;
  int t;
  int tmp, tmpc;
  xt a[100001];
  int b[100001];
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &(a[i].t), &(a[i].x));
    a[i].i = i;
  }
  qsort(a, n, sizeof(xt), st);
  t = 0;
  for (int i = 0; i < n; i += m) {
    if (i + m >= n) m = n - i;
    t = (t > a[i + m - 1].t) ? t : a[i + m - 1].t;
    qsort(a + i, m, sizeof(xt), sx);
    t += a[i].x;
    b[a[i].i] = t;
    tmpc = 1;
    int j;
    for (j = i + 1; j < i + m; ++j) {
      if (a[j].x == a[j - 1].x) {
        ++tmpc;
        b[a[j].i] = t;
      } else {
        t += (1 + tmpc / 2);
        t += a[j].x - a[j - 1].x;
        b[a[j].i] = t;
        tmpc = 1;
      }
    }
    t += (1 + tmpc / 2);
    t += a[j - 1].x;
  }
  printf("%d", b[0]);
  for (int i = 1; i < n; ++i) printf(" %d", b[i]);
  printf("\n");
  return 0;
}
