#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr i64 inf = i64(1E18);
struct node {
std::pair<i64, int> x1 = {inf, -1};
std::pair<i64, int> x2 = {inf, -1};
int lc = 0;
int rc = 0;
node() {}
};
std::vector<node> tree(1);
int new_node(int x) {
tree.emplace_back(tree[x]);
return int(tree.size()) - 1;
}
void pull(int v) {
tree[v].x1 = std::min(tree[tree[v].lc].x1, tree[tree[v].rc].x1);
tree[v].x2 = std::min(tree[tree[v].lc].x2, tree[tree[v].rc].x2);
}
int modify(int v, int l, int r, int p, i64 x1, i64 x2) {
int rv = new_node(v);
if (l == r) {
tree[rv].x1 = {x1, l};
tree[rv].x2 = {x2, l};
return rv;
}
int mid = (l + r) >> 1;
if (p <= mid) {
tree[rv].lc = modify(tree[v].lc, l, mid, p, x1, x2);
} else {
tree[rv].rc = modify(tree[v].rc, mid + 1, r, p, x1, x2);
}
pull(rv);
return rv;
}
std::pair<i64, int> get(int v, int l, int r, int ql, int qr, int t) {
if (!v || ql > qr) {
return {inf, -1};
}
if (l == r) {
return t == 0 ? tree[v].x1 : tree[v].x2;
}
int mid = (l + r) >> 1;
if (ql == l && r == qr) {
int lc = tree[v].lc;
int rc = tree[v].rc;
auto xl = t == 0 ? tree[lc].x1 : tree[lc].x2;
auto xr = t == 0 ? tree[rc].x1 : tree[rc].x2;
return std::min(xl, xr);
} else {
if (qr <= mid) {
return get(tree[v].lc, l, mid, ql, qr, t);
} else if (mid + 1 <= ql) {
return get(tree[v].rc, mid + 1, r, ql, qr, t);
} else {
return std::min(get(tree[v].lc, l, mid, ql, mid, t),
get(tree[v].rc, mid + 1, r, mid + 1, qr, t));
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, K;
std::cin >> N >> K;
std::vector<std::array<int, 2>> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i][0] >> A[i][1];
}
std::sort(A.begin(), A.end());
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
return A[lhs][1] < A[rhs][1];
});
debug(A);
debug(ord);
std::vector<int> iord(N);
for (int i = 0; i < N; ++i) {
iord[ord[i]] = i;
}
debug(iord);
std::vector<int> roots(N + 1);
for (int i = 0; i < N; ++i) {
roots[i + 1] = modify(roots[i], 0, N - 1, iord[i], -A[i][0] - A[i][1], -A[i][0] + A[i][1]);
}
auto get_min = [&](int x) -> std::pair<i64, int> {
auto x1 = get(roots[x], 0, N - 1, 0, iord[x] - 1, 0);
auto x2 = get(roots[x], 0, N - 1, iord[x] + 1, N - 1, 1);
x1.first += A[x][0] + A[x][1];
x2.first += A[x][0] - A[x][1];
debug(x, x1, x2);
return std::min(x1, x2);
};
min_pq<std::pair<std::pair<i64, int>, int>> pq;
for (int i = 0; i < N; ++i) {
pq.emplace(get_min(i), i);
}
for (int i = 0; i < K; ++i) {
auto[x1, id] = pq.top();
pq.pop();
debug(x1, id);
roots[id] = modify(roots[id], 0, N - 1, x1.second, inf, inf);
pq.emplace(get_min(id), id);
std::cout << x1.first << '\n';
}
return 0;
}
