#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<pair<int, int>> to;
  int x, y;
  int time = 0, cnt = 0;
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &x, &y);
    time = max(time, x);
    to.push_back(make_pair(y, i));
    cnt++;
    if (cnt == m) {
      sort(to.begin(), to.end());
      time += to[0].first;
      int tek = 0;
      ans[to[0].second] = time;
      tek = to[0].first;
      int c = 1;
      for (int j = 1; j < m; ++j) {
        if (to[j - 1].first == to[j].first) {
          ans[to[j].second] = time;
          c++;
        } else {
          time += 1 + c / 2;
          time += (to[j].first - tek);
          tek = to[j].first;
          c = 1;
          ans[to[j].second] = time;
        }
      }
      time += 1 + c / 2;
      time += to[m - 1].first;
      to.clear();
      cnt = 0;
    }
  }
  if (to.size() != 0) {
    sort(to.begin(), to.end());
    m = to.size();
    time += to[0].first;
    int tek = 0;
    ans[to[0].second] = time;
    tek = to[0].first;
    int c = 1;
    for (int j = 1; j < m; ++j) {
      if (to[j - 1].first == to[j].first) {
        ans[to[j].second] = time;
        c++;
      } else {
        time += 1 + c / 2;
        time += (to[j].first - tek);
        tek = to[j].first;
        c = 1;
        ans[to[j].second] = time;
      }
    }
    time += 1 + c / 2;
    time += to[m - 1].first;
    to.clear();
    cnt = 0;
  }
  for (int i = 0; i < n; ++i) {
    printf("%d ", ans[i]);
  }
  return 0;
}
