#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
using namespace std;
void solve() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(n);
  for (auto &it : a) {
    cin >> it.first >> it.second;
  }
  int cnt = 0, time = 0, pos = 0, it = 0;
  vector<int> ans(n);
  while (true) {
    int where = pos, mx = 0;
    vector<pair<int, int>> curr;
    for (int i = pos; i < min(n, where + m); ++i) {
      if (a[i].first > time) mx = max(a[i].first - time, mx);
      curr.push_back({a[i].second, i});
    }
    sort(curr.begin(), curr.end());
    time += mx;
    for (int j = 0; j < (int)curr.size(); ++j) {
      int k = j, cnt = 0;
      time += curr[j].first - (j - 1 >= 0 ? curr[j - 1].first : 0);
      while (k < (int)curr.size() && curr[j].first == curr[k].first) {
        ++cnt;
        ans[curr[k].second] = time;
        ++k;
      }
      time += cnt / 2 + 1;
      j = k - 1;
    }
    time += curr.back().first;
    pos += m;
    ++it;
    if (pos >= n) break;
  }
  for (int t : ans) cout << t << ' ';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
}
