#include <bits/stdc++.h>
using namespace std;
int n, m;
struct Stud {
  int t, x;
  int num;
  Stud() {}
  Stud(int _x, int _y, int _num) {
    t = _x;
    x = _y;
    num = _num;
  }
};
Stud a[100000];
int numInB[100000];
Stud b[100000];
int t[400000];
int ans[100000];
bool cmp(Stud& a, Stud& b) { return a.x < b.x; }
void update(int v, int tl, int tr, int pos, int val) {
  if (tl == tr) {
    t[v] = val;
  } else {
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
      update(v << 1, tl, tm, pos, val);
    else
      update((v << 1) + 1, tm + 1, tr, pos, val);
    t[v] = t[v << 1] + t[(v << 1) + 1];
  }
}
int query(int v, int tl, int tr) {
  if (tl == tr) {
    return tl;
  } else {
    int tm = (tl + tr) >> 1;
    if (t[v << 1] > 0)
      return query(v << 1, tl, tm);
    else
      return query((v << 1) + 1, tm + 1, tr);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  for (int i = 0; i < 400000; i++) {
    t[i] = 0;
  }
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i].t >> a[i].x;
    a[i].num = i;
  }
  for (int i = 0; i < n; i++) {
    b[i] = a[i];
  }
  sort(b, b + n, cmp);
  for (int i = 0; i < n; i++) {
    numInB[b[i].num] = i;
  }
  int currT = 0;
  int currS = 0;
  vector<int> pending;
  while (currS != n) {
    for (int i = currS; i < min(currS + m, n); i++) {
      update(1, 0, n - 1, numInB[i], 1);
    }
    currT = max(currT, a[min(currS + m, n) - 1].t);
    int currX = 0;
    int cnt = 0;
    for (int i = currS; i < min(currS + m, n); i++) {
      int ptInB = query(1, 0, n - 1);
      int x = b[ptInB].x;
      if (x == currX)
        pending.push_back(ptInB);
      else {
        for (int j = 0; j < pending.size(); j++) {
          ans[b[pending[j]].num] = currT;
        }
        if (pending.size() != 0) currT += 1 + pending.size() / 2;
        pending.clear();
        currT += x - currX;
        currX = x;
        pending.push_back(ptInB);
      }
      update(1, 0, n - 1, ptInB, 0);
    }
    if (pending.size() != 0) {
      for (int j = 0; j < pending.size(); j++) {
        ans[b[pending[j]].num] = currT;
      }
      currT += 1 + pending.size() / 2;
      pending.clear();
    }
    currS = min(currS + m, n);
    currT += currX;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}
