#include <bits/stdc++.h>
const int N = 100010;
struct unit {
  int x, pos;
  bool operator<(const unit &A) const { return x < A.x; }
} tmp[N];
int ans[N];
int main() {
  int n, m, now = 0, man = 0, ti;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    man++;
    scanf("%d%d", &ti, &tmp[man].x);
    tmp[man].pos = i;
    if (now < ti) now = ti;
    if (man == m || i == n) {
      std::sort(tmp + 1, tmp + 1 + man);
      int last = 0;
      for (int j = 1; j <= man; j++) {
        now += tmp[j].x - last;
        int val = 1, k = j;
        while (j + 1 <= man && tmp[j].x == tmp[j + 1].x) val++, j++;
        for (; k <= j; k++) ans[tmp[k].pos] = now;
        now += val / 2 + 1;
        last = tmp[j].x;
      }
      if (i != n) now += last;
      man = 0;
    }
  }
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
  scanf(" ");
}
