#include <bits/stdc++.h>
using namespace std;
long long int n, m, cn[100010], yy = 0, a[100010];
pair<int, int> p[100010];
int main() {
  p[0].first = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> p[i].first;
    p[i].second = i;
  }
  int su = m, q = 0, k = 1, l = 0;
  for (int i = 1; i <= n; i++) {
    if (su == m) {
      sort(p + i, p + min(i + m, n + 1));
      su = 0;
      l = max(a[min(i + m - 1, n)], yy + p[i - 1].first + q);
      q = 0;
    }
    if (p[i].first == p[i + 1].first && su != m - 1 && i != n) {
      k++;
      cn[p[i].second] = l + p[i].first + q;
      yy = max(yy, cn[p[i].second] - q);
    } else {
      cn[p[i].second] = l + p[i].first + q;
      yy = max(yy, cn[p[i].second] - q);
      q += 1 + (k / 2);
      k = 1;
    }
    su++;
  }
  for (int i = 1; i <= n; i++) cout << cn[i] << " ";
}
