#include <bits/stdc++.h>
using namespace std;
struct st {
  int index, t, x, out;
} a[1000005];
int cmpx(st x1, st x2) { return x1.x < x2.x; }
int cmpi(st x1, st x2) { return x1.index < x2.index; }
int main() {
  int k, m, n;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i].t >> a[i].x;
    a[i].index = i;
  }
  int kol = (n + m - 1) / m;
  int tim = 0;
  for (int i = 0; i < kol; i++) {
    int i0 = i * m;
    int i1 = min((i + 1) * m, n);
    int x0 = 0;
    tim = max(tim, a[i1 - 1].t);
    sort(a + i0, a + i1, cmpx);
    int h = 1;
    for (int j = i0; j < i1; j++) {
      if (a[j + 1].x == a[j].x && (j + 1) < i1)
        h++;
      else {
        tim += a[j].x - x0;
        for (int ii = 0; ii < h; ii++) a[j - ii].out = tim;
        tim += (h / 2) + 1;
        x0 = a[j].x;
        h = 1;
      }
    }
    tim += a[i1 - 1].x;
  }
  sort(a, a + n, cmpi);
  for (int j = 0; j < n; j++) cout << a[j].out << " ";
  return 0;
}
