#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#define int ll // sry
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
const int INF = 1e18;
const int MAXN = 250'000;
struct Point {
int x, y;
};
struct Event {
int x, l, r, sign;
bool operator < (const Event &other) const {
return x != other.x? x < other.x : std::abs(sign) < std::abs(other.sign);
};
};
struct Fenwick {
std::vector<int> aib;
int n;
void init(int _n) {
n = _n + 1;
aib.assign(n, 0);
}
void update(int p, int v) {
for (; p < n; p += p & -p) {
aib[p] += v;
}
}
int query(int p) {
int ret = 0;
for (; p > 0; p -= p & -p) {
ret += aib[p];
}
return ret;
}
};
std::set<int> aint[4 * 3 * MAXN + 15]; // trust the process
std::set<std::pair<int, int>> have;
void update(int node, int tl, int tr, int l, int r, int id, int type) {
if (l <= tl && tr <= r) {
if (type == +1) {
aint[node].insert(id);
} else {
aint[node].erase(id);
}
} else {
int mid = (tl + tr) / 2;
if (l <= mid) {
update(2 * node, tl, mid, l, r, id, type);
}
if (mid < r) {
update(2 * node + 1, mid + 1, tr, l, r, id, type);
}
}
}
void collect(int node, int tl, int tr, int q, int id) {
for (int p : aint[node]) {
if (p < id) {
have.insert({p, id});
} else if (id < p) {
have.insert({id, p});
}
}
if (tl == tr) {
return;
}
int mid = (tl + tr) / 2;
if (q <= mid) {
collect(2 * node, tl, mid, q, id);
} else {
collect(2 * node + 1, mid + 1, tr, q, id);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, k;
std::cin >> n >> k;
std::vector<Point> a(n);
std::vector<Point> og(n);
for (int i = 0; i < n; i++) {
int x, y;
std::cin >> x >> y;
og[i] = {x, y};
a[i] = {x - y, x + y};
}
Fenwick aib;
aib.init(3 * n + 1);
auto countPairs = [&](int d) {
std::vector<Event> events;
std::vector<int> norm;
for (int i = 0; i < n; i++) {
events.push_back({a[i].x + d, a[i].y - d, a[i].y + d, +1});
events.push_back({a[i].x - d - 1, a[i].y - d, a[i].y + d, -1});
events.push_back({a[i].x, a[i].y, 0, 0});
norm.push_back({a[i].y - d});
norm.push_back({a[i].y});
norm.push_back({a[i].y + d});
}
norm.push_back(-INF);
std::sort(norm.begin(), norm.end());
norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
std::sort(events.begin(), events.end());
ll ret = 0;
aib.init(3 * n + 1);
for (auto [x, l, r, t] : events) {
l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin();
r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin();
if (t == 0) {
aib.update(l, +1);
} else {
ret += (aib.query(r) - aib.query(l - 1)) * t;
}
}
ret -= n;
return ret / 2;
};
int l = 0, r = 5e9;
while (l < r) {
int mid = (l + r) / 2;
if (countPairs(mid) >= k) {
r = mid;
} else {
l = mid + 1;
}
}
// ok cred ca era mult mai penal daca doar normalizam si faceam un pst dar oh well hai sa incerc sa bag asta
int d = r;
std::vector<Event> events;
std::vector<int> norm;
norm.push_back(-INF);
for (int i = 0; i < n; i++) {
events.push_back({a[i].x - d, a[i].y - d, a[i].y + d, +(i + 1)});
events.push_back({a[i].x + d + 1, a[i].y - d, a[i].y + d, -(i + 1)});
events.push_back({a[i].x, a[i].y, i + 1, 0});
norm.push_back(a[i].y - d);
norm.push_back(a[i].y);
norm.push_back(a[i].y + d);
}
std::sort(norm.begin(), norm.end());
norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
std::sort(events.begin(), events.end());
for (auto [x, l, r, t] : events) {
l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin();
int i;
if (t) {
i = std::abs(t) - 1;
t /= std::abs(t);
r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin();
} else {
i = r - 1;
}
if (t == 0) {
int p = std::lower_bound(norm.begin(), norm.end(), a[i].y) - norm.begin();
collect(1, 1, 3 * n, p, i);
} else {
update(1, 1, 3 * n, l, r, i, t);
}
assert((int) have.size() <= k + 5 * n);
}
std::vector<int> answer;
for (const auto &[x, y] : have) {
answer.push_back(std::abs(og[x].x - og[y].x) + std::abs(og[x].y - og[y].y));
}
std::sort(answer.begin(), answer.end());
answer.resize(k);
for (int x : answer) {
std::cout << x << ' ';
}
return 0;
}
