#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
struct my {
  int x, t, i, tt;
};
bool cmpi(my a, my b) { return a.i < b.i; }
bool cmpx(my a, my b) { return a.x < b.x; }
int main() {
  ios::sync_with_stdio(0);
  int n, m;
  my a[100013];
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i].t >> a[i].x;
    a[i].i = i;
  }
  int tl = 0;
  for (int i = 0; i < n; i += m) {
    int ir = min(i + m, n);
    tl = max(tl, a[ir - 1].t);
    sort(a + i, a + ir, cmpx);
    int tt = 0;
    for (int j = i; j < ir; j++) {
      if (j > i && a[j].x == a[j - 1].x) {
        a[j].tt = a[j - 1].tt;
      } else {
        int k = j;
        while (k < ir && a[j].x == a[k].x) k++;
        a[j].tt = tl + a[j].x + tt;
        tt += 1 + (k - j) / 2;
      }
    }
    tl += tt + a[ir - 1].x * 2;
  }
  sort(a, a + n, cmpi);
  for (int i = 0; i < n; i++) cout << a[i].tt << ' ';
  return 0;
}
