#include <bits/stdc++.h>
using namespace std;
int ans[100001], n, m, c;
pair<pair<int, int>, int> p[100001];
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> p[i].first.second >> p[i].first.first;
    p[i].second = i;
  }
  for (int i = 0; i < n; ++i) {
    int g = i;
    map<int, int> mp;
    while (g < n && g - i != m) {
      if (mp.find(p[g].first.first) == mp.end())
        mp[p[g].first.first] = 1;
      else
        mp[p[g].first.first]++;
      ++g;
    }
    if (p[g - 1].first.second > c) c = p[g - 1].first.second;
    sort(p + i, p + g);
    c += p[i].first.first;
    for (int j = i; j < g; ++j) {
      ans[p[j].second] = c;
      if (j != g - 1 && p[j].first.first != p[j + 1].first.first) {
        c += 1 + mp[p[j].first.first] / 2;
        c += p[j + 1].first.first - p[j].first.first;
      } else if (j == g - 1)
        c += 1 + mp[p[j].first.first] / 2;
    }
    c += p[g - 1].first.first;
    i = g - 1;
  }
  for (int i = 0; i < n; ++i) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
