#include <bits/stdc++.h>
using ll = long long;
template <class T> using Vec = std::vector<T>;
template <class T> using Rc = std::shared_ptr<const T>;
template <class T> using Heap = std::priority_queue<T, Vec<T>, std::greater<T>>;
constexpr int INF = std::numeric_limits<int>::max();
int scan() {
int x;
std::scanf("%d", &x);
return x;
}
void print(const ll x) {
std::printf("%lld\n", x);
}
struct Node;
using Ptr = Rc<Node>;
struct Node {
int left, right;
std::pair<int, int> value;
Ptr lch, rch;
explicit Node(const int i, const int x = -INF) : left(i), right(i + 1), value(x, i), lch(), rch() {}
explicit Node(const Ptr& l, const Ptr& r) : left(l -> left), right(r -> right), value(std::max(l -> value, r -> value)), lch(l), rch(r) {}
};
Ptr build(const int l, const int r) {
if (l + 1 == r) return std::make_shared<Node>(l);
const int m = (l + r) / 2;
return std::make_shared<Node>(build(l, m), build(m, r));
}
Ptr assign(const Ptr& n, const int i, const int x) {
if (n -> left == i and n -> right == i + 1) return std::make_shared<Node>(i, x);
if (i < n -> lch -> right) return std::make_shared<Node>(assign(n -> lch, i, x), n -> rch);
else return std::make_shared<Node>(n -> lch, assign(n -> rch, i, x));
}
std::pair<int, int> fold(const Ptr& n, const int l, const int r) {
if (r <= n -> left or n -> right <= l) return {-INF, -INF};
if (l <= n -> left and n -> right <= r) return n -> value;
return std::max(fold(n -> lch, l, r), fold(n -> rch, l, r));
}
int main() {
const int N = scan();
int K = scan();
Vec<std::pair<int, int>> Pts(N);
for (auto& [x, y] : Pts) {
x = scan();
y = scan();
}
std::sort(Pts.begin(), Pts.end());
Vec<int> idx(N);
{
Vec<std::pair<int, int>> cmp;
cmp.reserve(N);
for (int i = 0; i < N; ++i) {
cmp.emplace_back(Pts[i].second, i);
}
std::sort(cmp.begin(), cmp.end());
for (int i = 0; i < N; ++i) {
idx[cmp[i].second] = i;
}
}
Vec<Ptr> seg1(N), seg2(N);
seg1[0] = seg2[0] = build(0, N);
for (int i = 0; i < N - 1; ++i) {
seg1[i + 1] = assign(seg1[i], idx[i], (Pts[i].first - Pts[i].second));
seg2[i + 1] = assign(seg2[i], idx[i], (Pts[i].first + Pts[i].second));
}
Heap<std::tuple<ll, int, int>> heap;
for (int i = 1; i < N; ++i) {
{
const auto [x, j] = fold(seg1[i], idx[i], N);
if (x != -INF) {
heap.emplace((ll) (Pts[i].first - Pts[i].second) - (ll) x, i, j);
}
}
{
const auto [x, j] = fold(seg2[i], 0, idx[i]);
if (x != -INF) {
heap.emplace((ll) (Pts[i].first + Pts[i].second) - (ll) x, i, j);
}
}
}
while (K > 0) {
const auto [x, i, j] = heap.top();
heap.pop();
print(x);
K -= 1;
if (j >= idx[i]) {
seg1[i] = assign(seg1[i], j, -INF);
const auto [x, j] = fold(seg1[i], idx[i], N);
if (x != -INF) {
heap.emplace((ll) (Pts[i].first - Pts[i].second) - (ll) x, i, j);
}
} else {
seg2[i] = assign(seg2[i], j, -INF);
const auto [x, j] = fold(seg2[i], 0, idx[i]);
if (x != -INF) {
heap.emplace((ll) (Pts[i].first + Pts[i].second) - (ll) x, i, j);
}
}
}
return 0;
}
