#include <bits/stdc++.h>
using namespace std;
int n, m;
int i, j;
pair<int, int> students[100005];
int curTime;
int curX;
int res[100005];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (i = 0; i < n; ++i) cin >> students[i].first >> students[i].second;
  int lastStudent = 0;
  int firstStudent = 0;
  int k = 0;
  curX = 0;
  curTime = 0;
  while (lastStudent < n) {
    curX = 0;
    while (lastStudent < n && lastStudent - firstStudent < m) lastStudent++;
    if (curTime < students[lastStudent - 1].first)
      curTime = students[lastStudent - 1].first;
    set<pair<int, int> > container;
    for (i = firstStudent; i < lastStudent; ++i)
      container.insert(make_pair(students[i].second, i));
    set<pair<int, int> >::iterator jt;
    set<pair<int, int> >::iterator it;
    i = j = firstStudent;
    for (it = container.begin(); it != container.end();) {
      curTime += (*it).first - curX;
      curX = (*it).first;
      for (jt = it; jt != container.end() && (*jt).first == (*it).first; ++jt)
        res[(*jt).second] = curTime, j++;
      k = j - i;
      curTime += 1 + k / 2;
      it = jt;
      i = j;
    }
    curTime += curX;
    firstStudent = lastStudent;
  }
  for (i = 0; i < n; ++i) cout << res[i] << " ";
  cout << endl;
  return 0;
}
