#include <bits/stdc++.h>
using namespace std;
int n, m;
int x[100010], t[100010];
int ans[100010];
int solve(int cur, vector<pair<int, int> > v) {
  sort(v.begin(), v.end());
  int last = 0;
  for (int i = 0; i < v.size(); i++) {
    int tmp = v[i].first - last;
    int j = i;
    int tot = 0;
    while (v[j].first == v[i].first) {
      ans[v[j].second] = cur + tmp;
      tot++;
      j++;
    }
    cur += tmp + 1 + tot / 2;
    i = j - 1;
    last = v[i].first;
  }
  return cur + v[v.size() - 1].first;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) scanf("%d%d", &t[i], &x[i]);
  vector<pair<int, int> > v;
  int k = 0;
  int cur = 0;
  while (k < n) {
    v.clear();
    for (int i = k; i < min(k + m, n); i++) {
      v.push_back(make_pair(x[i], i));
      cur = max(cur, t[i]);
    }
    k += m;
    cur = solve(cur, v);
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  return 0;
}
