#include <bits/stdc++.h>
using namespace std;
int n, m;
void show(const vector<pair<int, pair<int, int> > >& a) {
  int sz = (int)a.size();
  cerr << "current vector : " << endl;
  for (int i = 0; i < sz; ++i) {
    cerr << a[i].first << " " << a[i].second.first << " " << a[i].second.second
         << endl;
  }
}
bool comp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
  return (a.second.first < b.second.first);
}
int main() {
  pair<int, pair<int, int> > stud;
  vector<pair<int, pair<int, int> > > studs, studpos;
  vector<pair<int, pair<int, int> > >::iterator it1, it2;
  cin >> n >> m;
  long long timeout[n], globaladd = 0, curplace;
  int i, j, p, k, taxi[m];
  for (i = 0; i < n / m; ++i) {
    for (j = 0; j < m; ++j) {
      cin >> stud.first >> stud.second.first;
      stud.second.second = i * m + j;
      studs.push_back(stud);
    }
    if (globaladd < studs[j - 1].first) {
      globaladd = studs[j - 1].first;
    }
    sort(studs.begin(), studs.end(), comp);
    for (j = 0; j < m;) {
      k = 1;
      p = j;
      curplace = studs[j].second.first;
      taxi[j] = studs[j].second.second;
      ++j;
      while (j < m - 1 and curplace == studs[j].second.first) {
        taxi[j] = studs[j].second.second;
        ++k;
        ++j;
      }
      if (j == m - 1)
        if (curplace == studs[j].second.first) {
          taxi[j] = studs[j].second.second;
          ++k;
          ++j;
        }
      for (; p < j; ++p) {
        timeout[taxi[p]] = curplace + globaladd;
      }
      globaladd += k / 2 + 1;
    }
    globaladd += 2 * curplace;
    studs.clear();
  }
  i *= m;
  m = n % m;
  if (m > 0) {
    for (j = 0; j < m; ++j) {
      cin >> stud.first >> stud.second.first;
      stud.second.second = i + j;
      studs.push_back(stud);
    }
    if (globaladd < studs[j - 1].first) {
      globaladd = studs[j - 1].first;
    }
    sort(studs.begin(), studs.end(), comp);
    for (j = 0; j < m;) {
      k = 1;
      p = j;
      curplace = studs[j].second.first;
      taxi[j] = studs[j].second.second;
      ++j;
      while (j < m - 1 and curplace == studs[j].second.first) {
        taxi[j] = studs[j].second.second;
        ++k;
        ++j;
      }
      if (j == m - 1)
        if (curplace == studs[j].second.first) {
          taxi[j] = studs[j].second.second;
          ++k;
          ++j;
        }
      for (; p < j; ++p) {
        timeout[taxi[p]] = curplace + globaladd;
      }
      globaladd += 1 + k / 2;
    }
  }
  for (i = 0; i < n; ++i) {
    cout << timeout[i] << " ";
  }
  cout << endl;
  return 0;
}
