#include <bits/stdc++.h>
using namespace std;
struct student {
  int t, x, idx;
};
int N, M;
student a[1 << 17];
int ans[1 << 17];
void scan() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; ++i) {
    scanf("%d%d", &a[i].t, &a[i].x);
    a[i].idx = i;
  }
}
int f(student t1, student t2) { return t1.x < t2.x; }
void solve() {
  int res = 0;
  for (int i = 0; i < N; i += M) {
    int last = i + M - 1;
    last = min(last, N - 1);
    res = max(res, a[last].t);
    sort(a + i, a + last + 1, f);
    int cnt = 1;
    for (int j = i + 1; j <= last; ++j)
      if (a[j].x == a[j - 1].x)
        ++cnt;
      else {
        int idx = j - 1;
        while (idx >= i) {
          ans[a[idx].idx] = res + a[idx].x;
          if (idx == 0) break;
          if (a[idx].x == a[idx - 1].x)
            --idx;
          else
            break;
        }
        res += (cnt / 2 + 1);
        cnt = 1;
      }
    int idx = last;
    while (idx >= i) {
      ans[a[idx].idx] = res + a[idx].x;
      if (idx == 0) break;
      if (a[idx].x == a[idx - 1].x)
        --idx;
      else {
        break;
      }
    }
    res += (cnt / 2 + 1);
    res += (a[last].x * 2);
  }
  for (int i = 0; i < N; ++i) printf("%d ", ans[i]);
  printf("\n");
}
int main() {
  scan();
  solve();
}
