#include <bits/stdc++.h>
using namespace std;
int x[100004], t[100004], ans[100004];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (n); i++) scanf("%d%d", &t[i], &x[i]);
  int cur = 0;
  for (int i = 0; i < n;) {
    int j = min(i + m, n);
    map<int, vector<int> > u;
    for (int k = i; k < j; k++) {
      cur = max(cur, t[k]);
      u[x[k]].push_back(k);
    }
    int last = 0;
    for (map<int, vector<int> >::iterator it = u.begin(); it != u.end(); ++it) {
      cur += it->first - last;
      for (vector<int>::iterator jt = it->second.begin();
           jt != it->second.end(); ++jt)
        ans[*jt] = cur;
      cur += it->second.size() / 2 + 1;
      last = it->first;
    }
    cur += last;
    i = j;
  }
  for (int i = 0; i < (n); i++) printf("%d%c", ans[i], " \n"[i + 1 == n]);
  return 0;
}
