#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, s, p, x[100001], t[100001], w[100001];
void sort1(int l, int r) {
  int i, j, y, z;
  i = l;
  j = r;
  y = x[(l + r) / 2];
  do {
    while (x[i] < y) {
      i++;
    }
    while (x[j] > y) {
      j--;
    }
    if (!(i > j)) {
      z = x[i];
      x[i] = x[j];
      x[j] = z;
      z = t[i];
      t[i] = t[j];
      t[j] = z;
      i++;
      j--;
    }
  } while (!(i > j));
  if (l < j) {
    sort1(l, j);
  }
  if (i < r) {
    sort1(i, r);
  }
}
void sort2(int l, int r) {
  int i, j, y, z;
  i = l;
  j = r;
  y = t[(l + r) / 2];
  do {
    while (t[i] < y) {
      i++;
    }
    while (t[j] > y) {
      j--;
    }
    if (!(i > j)) {
      z = x[i];
      x[i] = x[j];
      x[j] = z;
      z = t[i];
      t[i] = t[j];
      t[j] = z;
      z = w[i];
      w[i] = w[j];
      w[j] = z;
      i++;
      j--;
    }
  } while (!(i > j));
  if (l < j) {
    sort2(l, j);
  }
  if (i < r) {
    sort2(i, r);
  }
}
int main() {
  scanf("%d %d\n", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d %d\n", &t[i], &x[i]);
  }
  i = m;
  s = 0;
  while (i <= n) {
    s = max(s, t[i]);
    sort1(i - m + 1, i);
    p = x[i];
    k = 1;
    w[i - m + 1] = s + x[i - m + 1];
    for (j = i - m + 2; j <= i; j++) {
      if (x[j] == x[j - 1]) {
        k++;
      } else {
        s += 1 + (k / 2);
        k = 1;
      }
      w[j] = s + x[j];
    }
    s += p + 1 + p + (k / 2);
    i += m;
  }
  if (i - m < n) {
    s = max(s, t[n]);
    sort1(i - m + 1, n);
    p = x[n];
    k = 1;
    w[i - m + 1] = s + x[i - m + 1];
    for (j = i - m + 2; j <= n; j++) {
      if (x[j] == x[j - 1]) {
        k++;
      } else {
        s += 1 + k / 2;
        k = 1;
      }
      w[j] = s + x[j];
    }
    s += p + 1 + p + k / 2;
  }
  sort2(1, n);
  for (i = 1; i <= n; i++) {
    printf("%d ", w[i]);
  }
  return 0;
}
