#include <bits/stdc++.h>
using namespace std;
int x[100005], t[100005], res[100005];
pair<int, int> p[100005];
int main() {
  int n, m;
  int base = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", t + i, x + i);
    p[i] = make_pair(x[i], i);
    if (i % m == 0) {
      base = max(base, t[i]);
      sort(p + i - m + 1, p + i + 1);
      int pre = i - m + 1, pt = 0;
      for (int j = i - m + 1; j <= i;) {
        while (p[pre].first == p[j].first) {
          ++j;
        }
        base += p[pre].first - pt;
        int deta = j - pre;
        pt = p[pre].first;
        while (pre < j) {
          res[p[pre].second] = base;
          ++pre;
        }
        base += deta / 2 + 1;
      }
      base += p[i].first;
    } else if (i == n) {
      base = max(base, t[i]);
      sort(p + n / m * m + 1, p + i + 1);
      int pre = n / m * m + 1, pt = 0;
      for (int j = n / m * m + 1; j <= i;) {
        while (p[pre].first == p[j].first) {
          ++j;
        }
        base += p[pre].first - pt;
        int deta = j - pre;
        pt = p[pre].first;
        while (pre < j) {
          res[p[pre].second] = base;
          ++pre;
        }
        base += deta / 2 + 1;
      }
      base += p[i].first;
    }
  }
  for (int i = 1; i <= n; ++i) printf("%d ", res[i]);
  return 0;
}
