#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
const int M = 1000000007;
const double PI = atan(1) * 4;
const int oo = 1000000000;
int n, m, v[N][2], ans[N], t = 0, cap = 0;
map<int, vector<int> > cur;
map<int, vector<int> >::iterator it;
void go() {
  int ls = 0;
  for (it = cur.begin(); it != cur.end(); ++it) {
    vector<int> &d = it->second;
    t += it->first - ls;
    ls = it->first;
    for (int i = 0; i < d.size(); ++i) ans[d[i]] = t;
    t += 1 + (int)d.size() / 2;
  }
  t += ls;
  cur.clear();
  cap = 0;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) scanf("%d%d", &v[i][0], &v[i][1]);
  for (int i = 0; i < n; ++i) {
    if (cap == m) go();
    t = max(t, v[i][0]);
    cur[v[i][1]].push_back(i);
    ++cap;
  }
  if (cap) go();
  for (int i = 0; i < n; ++i) printf("%d ", ans[i]);
}
