#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
struct student {
  int t, x, id;
  bool operator<(const student &b) const { return x < b.x; }
} a[N];
int n, m, ans[N];
vector<student> bus;
int main() {
  int i, j, time = 0, k, x, t;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d%d", &a[i].t, &a[i].x), a[i].id = i;
  for (i = 1; i <= n; i++) {
    time = max(time, a[i].t);
    bus.push_back(a[i]);
    if (bus.size() == m || i == n) {
      sort(bus.begin(), bus.end());
      x = 0;
      for (j = 0; j < bus.size(); j++) {
        for (k = j; bus[j].x == bus[k].x && k < bus.size(); k++)
          ;
        k--;
        time += bus[j].x - x;
        x = bus[j].x;
        t = j;
        for (; j <= k; j++) ans[bus[j].id] = time;
        time += (k - t + 1) / 2 + 1;
        j = k;
      }
      time += x;
      bus.clear();
    }
  }
  for (i = 1; i <= n; i++) printf("%d ", ans[i]);
}
