#include <bits/stdc++.h>
using namespace std;
struct student {
  int i, t, x;
  bool operator<(const student &s) const { return x < s.x; }
};
int n, m;
student sts[100009], bus[100009];
int ret[100009];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    sts[i].i = i;
    scanf("%d%d", &sts[i].t, &sts[i].x);
  }
  int t = 0, cur = 0;
  while (cur < n) {
    int s = 0;
    while (s < m && cur < n) {
      bus[s] = sts[cur++];
      t = max(t, bus[s].t);
      s++;
    }
    sort(bus, bus + s);
    int x = 0;
    for (int i = 0; i < s; ++i) {
      int j = i + 1;
      while (j < s && bus[i].x == bus[j].x) {
        j++;
      }
      int k = (j - i);
      t += bus[i].x - x;
      x = bus[i].x;
      while (i < j) {
        ret[bus[i].i] = t;
        i++;
      }
      t += 1 + k / 2;
      i--;
    }
    t += x;
  }
  for (int i = 0; i < n; ++i) {
    if (i) {
      printf(" ");
    }
    printf("%d", ret[i]);
  }
  printf("\n");
  return 0;
}
