#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> vx(n);
  vector<int> res(n);
  int T = 0;
  for (int i = 0; i < n; ++i) {
    int t;
    scanf("%d%d", &t, &vx[i]);
    if ((i + 1) % m == 0 || i == n - 1) {
      T = max(T, t);
      int cur = i - i % m;
      vector<pair<int, int> > v;
      for (int j = cur; j <= i; ++j) v.push_back(make_pair(vx[j], j));
      sort((v).begin(), (v).end());
      int p = 0;
      int x = 0;
      while (p < ((int)(v).size())) {
        T += v[p].first - x;
        ;
        x = v[p].first;
        int q = p;
        while (q < ((int)(v).size()) && v[q].first == v[p].first) {
          res[v[q].second] = T;
          ++q;
        }
        int dt = 1 + (q - p) / 2;
        T += dt;
        p = q;
      }
      T += x;
    }
  }
  for (int i = 0; i < ((int)(res).size()); ++i) printf("%d ", res[i]);
  printf("\n");
  return 0;
}
