#include <bits/stdc++.h>
using namespace std;
struct Students {
  int arrive, off, x, id;
  static bool byX(const Students &a, const Students &b) { return a.x < b.x; }
  static bool byID(const Students &a, const Students &b) { return a.id < b.id; }
} s[100010];
int main() {
  int n, m;
  while (cin >> n >> m) {
    for (int i = 0; i < n; ++i) {
      cin >> s[i].arrive >> s[i].x;
      s[i].id = i;
    }
    int time = 0;
    for (int k = 0; k < n; k += m) {
      int last = min(n, k + m), lastx = 0, i = k;
      time = max(time, s[last - 1].arrive);
      sort(s + k, s + last, Students::byX);
      while (i < last) {
        time += s[i].x - lastx;
        lastx = s[i].x;
        int cnt = 0;
        do {
          s[i].off = time;
          ++cnt, ++i;
        } while (i < last && s[i].x == s[i - 1].x);
        time += 1 + cnt / 2;
      }
      time += s[last - 1].x;
    }
    sort(s, s + n, Students::byID);
    for (int i = 0; i < n - 1; ++i) {
      cout << s[i].off << ' ';
    }
    cout << s[n - 1].off << endl;
  }
  return 0;
}
