#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int> > > s;
vector<pair<int, pair<int, int> > > b;
int res[100000];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    s.push_back(make_pair(b, make_pair(a, i)));
  }
  int now = 0;
  for (int i = 0; i < n;) {
    b.clear();
    int pos = 0;
    while (i < n && b.size() < m) b.push_back(s[i++]);
    if (now < b[b.size() - 1].second.first) now = b[b.size() - 1].second.first;
    sort(b.begin(), b.end());
    for (int j = 0; j < b.size();) {
      int z = b[j].first;
      int c = 0, k = j;
      while (b[j].first == z && j < b.size()) ++j, ++c;
      now += z - pos;
      pos = z;
      while (k < j) res[b[k++].second.second] = now;
      now += 1 + c / 2;
    }
    now += pos;
  }
  for (int i = 0; i < n; ++i) printf("%d ", res[i]);
  printf("\n");
  return 0;
}
