#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
struct Students {
  int t;
  int x;
  int no;
  int T_left;
} S[MAX];
bool cmp(Students a, Students b) { return a.x < b.x; }
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &S[i].t, &S[i].x);
    S[i].no = i;
  }
  int T_return = 0;
  for (int t = 0; t < n / m + (n % m != 0); t++) {
    int base = t * m;
    int mxn = min(n, base + m);
    int BusStart = T_return;
    for (int i = base; i < mxn; i++) {
      BusStart = max(BusStart, S[i].t);
    }
    sort(S + base, S + mxn, cmp);
    int T_extra = 0;
    for (int i = base; i < mxn; i++) {
      int l = i;
      int r = i;
      int down_pos = S[l].x;
      while (r + 1 < mxn && S[r + 1].x == S[l].x) r++;
      int no_to_leave = r - l + 1;
      int TtoLeave = BusStart + T_extra + down_pos;
      for (int j = l; j <= r; j++) S[S[j].no].T_left = TtoLeave;
      T_extra += 1 + (no_to_leave / 2);
      if (r == base + m - 1) {
        T_return = BusStart + T_extra + down_pos * 2;
      }
      i = r;
    }
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", S[i].T_left);
  }
  puts("");
  return 0;
}
