#include <bits/stdc++.h>
using namespace std;
class bus {
 public:
  int x, t, ad;
};
bus d[101000];
int n, m, k = 1, res[101000], bt, A;
bool v[10100];
int ar[101000];
vector<int> yol[10100];
void Write() {
  int i;
  for (i = 1; i <= n; i++) printf("%d ", res[i]);
  printf("\n");
}
void Bosalt(int j) {
  int i;
  for (i = 1; i < j; i++) v[ar[i]] = 0;
}
void Solve() {
  int i, j, yer, maxi, c, t;
  while (A) {
    maxi = -1;
    j = 1;
    if (A > m) {
      for (i = k; i < k + m; i++) {
        yol[d[i].x].push_back(d[i].ad);
        maxi = max(maxi, d[i].x);
        if (v[d[i].x]) continue;
        ar[j++] = d[i].x;
        v[d[i].x] = 1;
      }
      k += m;
      A -= m;
    } else {
      for (i = k; i < k + A; i++) {
        yol[d[i].x].push_back(d[i].ad);
        maxi = max(maxi, d[i].x);
        if (v[d[i].x]) continue;
        ar[j++] = d[i].x;
        v[d[i].x] = 1;
      }
      k += A;
      A = 0;
    }
    sort(ar + 1, ar + j);
    if (bt < d[k - 1].t) bt = d[k - 1].t;
    yer = 0;
    for (i = 1; i < j; i++) {
      bt += ar[i] - yer;
      yer = ar[i];
      t = yol[ar[i]].size();
      for (c = 0; c < t; c++) res[yol[ar[i]][c]] = bt;
      bt += 1 + t / 2;
      yol[ar[i]].clear();
    }
    bt += maxi;
    if (A) Bosalt(j);
  }
}
bool cmp(bus a, bus b) { return a.t < b.t; }
void Read() {
  int i;
  scanf(" %d %d", &n, &m);
  A = n;
  for (i = 1; i <= n; i++) {
    scanf(" %d %d", &d[i].t, &d[i].x);
    d[i].ad = i;
  }
  sort(d + 1, d + n + 1, cmp);
}
int main() {
  Read();
  Solve();
  Write();
  return 0;
}
