#include <bits/stdc++.h>
using namespace std;
template <class T>
inline int cMin(T& a, T b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline int cMax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
inline string to_str(T v) {
  ostringstream os;
  os << v;
  return os.str();
}
const double pi = acos(-1.0);
const double eps = 1e-9;
template <class T>
inline T isqr(T v) {
  return v * v;
}
template <class T>
inline T iabs(T v) {
  return v < 0 ? -v : v;
}
template <class T>
inline int isgn(T v) {
  return iabs(v) <= eps ? 0 : (v < 0 ? -1 : 1);
}
template <typename T>
inline T next() {
  static char buf[64];
  scanf("%s", buf);
  istringstream is(buf);
  T v;
  is >> v;
  return v;
}
inline int nextInt() {
  int v = 0;
  scanf("%d", &v);
  return v;
}
int main(int argc, char* argv[]) {
  int N, M;
  scanf("%d%d", &N, &M);
  vector<int> Ans(N);
  map<int, vector<int> > hash;
  int Qn = 0, CurT = 0;
  for (int idx = 0; idx < N; ++idx) {
    int t, x;
    scanf("%d%d", &t, &x);
    CurT = max(CurT, t);
    hash[x].push_back(idx);
    ++Qn;
    if (idx == N - 1 || Qn == M) {
      map<int, vector<int> >::iterator it;
      int PreX = 0;
      for (it = hash.begin(); it != hash.end(); ++it) {
        int now = it->first - PreX + CurT;
        for (vector<int>::iterator j = it->second.begin();
             j != it->second.end(); ++j)
          Ans[*j] = now;
        now += 1 + (it->second.size() >> 1);
        CurT = now;
        PreX = it->first;
      }
      CurT += PreX;
      Qn = 0;
      hash.clear();
    }
  }
  for (int i = 0; i < N; ++i) {
    printf("%d%c", Ans[i], i == N - 1 ? '\n' : ' ');
  }
  return 0;
}
