#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int prime = 9241;
const long double pi = acos(-1.);
int t[100005], x[100005];
int ans[100005];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> t[i] >> x[i];
  int t0 = 0;
  for (int i = 0; i < n;) {
    vector<pair<int, int> > stud;
    for (; stud.size() < m && i < n; i++) stud.push_back(make_pair(x[i], i));
    t0 = max(t[i - 1], t0);
    sort(stud.begin(), stud.end());
    stud.push_back(make_pair(1000000000, -1));
    int cnt = 0;
    int wasx = 0;
    for (int j = 0; j < stud.size(); j++) {
      if (j == 0 || stud[j].first == stud[j - 1].first)
        cnt++;
      else {
        t0 += stud[j - 1].first - wasx;
        wasx = stud[j - 1].first;
        for (int k = j - 1; j >= 0 && wasx == stud[k].first; k--)
          ans[stud[k].second] = t0;
        t0 += cnt / 2 + 1;
        cnt = 1;
      }
    }
    t0 += stud[stud.size() - 2].first;
  }
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  cout << endl;
  return 0;
}
