#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int n, m;
int t[MAX_N], x[MAX_N];
int nxt;
int idx[MAX_N];
int res[MAX_N];
bool mycmp(const int a, const int b) {
  if (x[a] != x[b]) return x[a] < x[b];
  return a < b;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) scanf("%d%d", &t[i], &x[i]);
  int time = 0;
  for (int step = 0; step < n; step += m) {
    nxt = 0;
    for (int i = step; i < min(step + m, n); ++i) idx[nxt++] = i;
    time += max(0, t[idx[nxt - 1]] - time);
    sort(idx, idx + nxt, mycmp);
    for (int i = 0; i < nxt;) {
      int j = i;
      for (; j < nxt && x[idx[i]] == x[idx[j]]; ++j)
        ;
      time += x[idx[i]];
      if (i > 0) time -= x[idx[i - 1]];
      for (int k = i; k < j; ++k) res[idx[k]] = time;
      time += 1 + (j - i) / 2;
      i = j;
    }
    time += x[idx[nxt - 1]];
  }
  printf("%d", res[0]);
  for (int i = 1; i < n; ++i) printf(" %d", res[i]);
  printf("\n");
  return 0;
}
