#include <bits/stdc++.h>
using namespace std;
struct st {
  int t, x, id;
};
const int INF = 1000 * 1000 * 1000;
bool operator<(const st &a, const st &b) {
  return a.x < b.x || a.x == b.x && a.t < b.t;
}
int main() {
  st st_inf;
  st_inf.x = INF;
  st_inf.t = INF;
  st_inf.id = INF;
  int N, M;
  queue<st> ost;
  cin >> N >> M;
  st r;
  for (int i = 0; i < N; ++i) {
    scanf("%d%d", &r.t, &r.x);
    r.id = i;
    ost.push(r);
  }
  int OST = N;
  int BUS = 0;
  vector<st> bus;
  long long int T = 0;
  vector<long long int> R(100005);
  while (BUS || OST) {
    while (OST && BUS < M) {
      st t = ost.front();
      T = max(T, (long long int)t.t);
      bus.push_back(t);
      ost.pop();
      OST--;
      BUS++;
    }
    sort(bus.begin(), bus.end());
    queue<st> w;
    int y = 0;
    while (y < bus.size() && bus[y].t != INF) {
      w.push(bus[y]);
      y++;
    }
    BUS = 0;
    int L = 0;
    bus.clear();
    while (!w.empty()) {
      int X;
      X = w.front().x;
      int cnt_v = 1;
      R[w.front().id] = T + (X - L);
      w.pop();
      while (!w.empty()) {
        if (w.front().x == X) {
          R[w.front().id] = T + (X - L);
          w.pop();
          cnt_v++;
        } else {
          break;
        }
      }
      T += (X - L) + (int)(cnt_v / 2) + 1;
      L = X;
      if (w.empty()) {
        T += L;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    cout << R[i] << " ";
  }
  return 0;
}
