#include <bits/stdc++.h>
using namespace std;
struct Stu {
  int t, x, pos;
  void read(int _p) {
    cin >> t >> x;
    pos = _p;
  }
} st[1000020];
int n, m;
void init() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) st[i].read(i);
}
bool operator<(Stu a, Stu b) { return a.t > b.t; }
bool cmp2(Stu a, Stu b) { return a.t < b.t; }
bool cmp(Stu a, Stu b) { return a.x < b.x; }
priority_queue<Stu, vector<Stu> > PQ;
Stu V[1000020];
int ans[1000020];
int main() {
  init();
  sort(st + 1, st + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i) PQ.push(st[i]);
  int nowT(0), nowS(0);
  int tN = n;
  while (n) {
    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
      V[++cnt] = PQ.top();
      PQ.pop();
      if ((--n) == 0) break;
    }
    nowT = max(nowT, V[cnt].t);
    nowS = 0;
    sort(V + 1, V + cnt + 1, cmp);
    int i = 1;
    while (i <= cnt) {
      if (V[i].x > nowS) {
        nowT += V[i].x - nowS;
        nowS = V[i].x;
      }
      double time = 1.00000001;
      while (V[i].x == nowS && i <= cnt) {
        time += 0.500000001;
        ans[V[i].pos] = nowT;
        i++;
      }
      nowT += (int)time;
    }
    nowT += nowS;
  }
  cout << ans[1];
  for (int i = 2; i <= tN; ++i) printf(" %d", ans[i]);
  cout << endl;
}
