#include <bits/stdc++.h>
using namespace std;
int u = 1, i = 0, q1, q2, a[100001], s[200002], d[100000], f[100001];
void k(int w) {
  q2 = w / 2;
  while (a[s[q2]] > a[q1]) {
    s[w] = s[q2];
    w = q2;
    q2 /= 2;
  }
  s[w] = q1;
}
void l() {
  if (i) {
    i--;
    k(d[i]);
  } else {
    k(u);
    u++;
  }
}
void m() {
  q1 = 1;
  q2 = 2;
  while ((s[q2]) || (s[q2 + 1]))
    if ((s[q2]) && ((!s[q2 + 1]) || (a[s[q2]] < a[s[q2 + 1]]))) {
      s[q1] = s[q2];
      q1 = q2;
      q2 = q1 * 2;
    } else {
      s[q1] = s[q2 + 1];
      q1 = q2 + 1;
      q2 = q1 * 2;
    }
  s[q1] = 0;
  d[i] = q1;
  i++;
}
int main() {
  int q, w, e, r, t, c, v, y;
  a[0] = -1;
  for (w = 0; w < 200002; w++) s[w] = 0;
  cin >> q >> w;
  e = t = 0;
  r = 1;
  while ((e) || (r <= q)) {
    while ((e < w) && (r <= q)) {
      cin >> c >> a[r];
      if (t < c) t = c;
      q1 = r;
      l();
      r++;
      e++;
    }
    y = 0;
    while (e) {
      c = a[s[1]];
      t += c - y;
      v = 0;
      while (a[s[1]] == c) {
        f[s[1]] = t;
        m();
        e--;
        v++;
      }
      t += 1 + v / 2;
      y = c;
    }
    t += y;
  }
  for (e = 1; e <= q; e++) cout << f[e] << " ";
  return 0;
}
