#include <bits/stdc++.h>
using namespace std;
const int MN = 1000 * 100 + 10;
int n, m, t[MN], x[MN], ans[MN], curr_t = 0;
vector<pair<int, int> > sp;
void wait(int k) {
  int lst = min(n - 1, k + m - 1);
  curr_t = max(curr_t, t[lst]);
}
void boarding(int pos) {
  sp.clear();
  while (pos < n && sp.size() < m) {
    sp.push_back(make_pair(x[pos], pos));
    pos++;
  }
}
void go() {
  sort(sp.begin(), sp.end());
  int pos = 0, lst = 0;
  while (pos < sp.size()) {
    curr_t += (sp[pos].first - lst);
    int cnt = 0;
    while (pos + cnt < sp.size()) {
      if (sp[pos + cnt].first == sp[pos].first) {
        ans[sp[pos + cnt].second] = curr_t;
        cnt++;
      } else
        break;
    }
    lst = sp[pos].first;
    curr_t += (1 + cnt / 2);
    pos += cnt;
  }
  curr_t += lst;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) scanf("%d%d", &t[i], &x[i]);
  int k = 0;
  while (k < n) {
    wait(k);
    boarding(k);
    k += sp.size();
    go();
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
