#include <bits/stdc++.h>
using namespace std;
int n, m, M;
int i, j, k, l;
struct studentOfIMSFU {
  int t;
  int x;
  int i;
} s[100005];
long long w[100005], stupid_ctime;
int p[100005];
bool cmp(int i, int j) { return s[i].x < s[j].x; }
void runBus68() {
  stupid_ctime =
      ((stupid_ctime) > (s[p[m - 1]].t) ? (stupid_ctime) : (s[p[m - 1]].t));
  sort(p, p + m, cmp);
  int i, k, x, j;
  k = 0;
  x = 0;
  for (i = 0; i < m; ++i) {
    if (i == m - 1 || s[p[i]].x < s[p[i + 1]].x) {
      ++k;
      stupid_ctime += s[p[i]].x - x;
      for (j = i; j >= 0 && s[p[j]].x == s[p[i]].x; --j)
        w[s[p[j]].i] = stupid_ctime;
      x = s[p[i]].x;
      stupid_ctime += k / 2 + 1;
      k = 0;
    } else
      ++k;
  }
  stupid_ctime += x;
  m = 0;
}
int main() {
  scanf("%d%d", &n, &M);
  for (i = 0; i < n; ++i) {
    scanf("%d%d", &s[i].t, &s[i].x);
    s[i].i = i;
  }
  stupid_ctime = 0;
  for (i = 0; i < n; ++i) {
    p[m++] = i;
    if (m == M || i == n - 1) runBus68();
  }
  for (i = 0; i < n; ++i) printf("%I64d ", w[i]);
  return 0;
}
