#include <bits/stdc++.h>
using namespace std;
struct Student {
  int i, t, x;
  bool operator<(const Student& o) const { return x < o.x; }
} s[100000];
int p[100000];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i != n; ++i) {
    scanf("%d%d", &(s[i].t), &(s[i].x));
    s[i].i = i;
  }
  int c = 0, x;
  for (int l = 0; l < n; l += m) {
    int r = min(l + m, n);
    c = max(c, s[r - 1].t);
    x = 0;
    sort(s + l, s + r);
    int ll = l, rr = l;
    while (rr < r) {
      for (; rr < r && s[ll].x == s[rr].x; ++rr) {
        ;
      }
      c += s[ll].x - x;
      x = s[ll].x;
      for (int i = ll; i < rr; ++i) {
        p[s[i].i] = c;
      }
      c += 1 + (rr - ll) / 2;
      ll = rr;
    }
    c += s[r - 1].x;
  }
  for (int i = 0; i < n - 1; ++i) {
    printf("%d ", p[i]);
  }
  printf("%d\n", p[n - 1]);
  return 0;
}
