#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int> > st(n);
  for (int i = 0; i < n; ++i) cin >> st[i].first >> st[i].second;
  int t = 0;
  int i = 0;
  vector<int> d(n);
  for (int i = 0; i < n; ++i) {
    int cur = 0;
    vector<pair<int, int> > q;
    while (cur < m && cur + i < n) {
      q.push_back(make_pair(st[cur + i].second, cur + i));
      t = max(t, st[cur + i].first);
      cur++;
    }
    sort(q.begin(), q.end());
    int a = q[0].first;
    int b = q[0].second;
    d[b] = t + a;
    t = d[b];
    int c = 1;
    for (int j = 1; j < q.size(); ++j) {
      if (q[j].first == a) {
        c++;
        d[q[j].second] = d[b];
        i++;
      } else {
        d[q[j].second] = d[b] + 1 + c / 2 + (q[j].first - a);
        t = d[q[j].second];
        a = q[j].first;
        b = q[j].second;
        i++;
        c = 1;
      }
    }
    t += a + (1 + c / 2);
  }
  for (int i = 0; i < n; ++i) cout << d[i] << ' ';
  cout << endl;
}
