#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int i, int delta) {
for (i++; i <= n; i += i & -i) {
bit[i] += delta;
}
}
int sum(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<array<int, 2>> a(n);
vector<long long> ys;
for (int i = 0; i < n; i++) {
int x0, y0;
cin >> x0 >> y0;
int x = x0 - y0;
int y = x0 + y0;
a[i] = {x, y};
ys.push_back(y);
}
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
int C = ys.size();
auto countPair = [&ys, &C, &a](long long dist) -> long long { // returns number of pairs with distance <= 'dist'
vector<array<long long, 4>> events; // {x, erase:1 insert:0, y}
for (auto [x, y] : a) {
events.push_back({x, 0, x, y});
events.push_back({x + dist, 1, x, y});
}
sort(events.begin(), events.end());
Fenwick fen(C);
long long res = 0;
for (auto [t, type, x, y] : events) {
if (type == 0) {
res += fen.sum(upper_bound(ys.begin(), ys.end(), y + dist) - ys.begin()) - fen.sum(lower_bound(ys.begin(), ys.end(), y - dist) - ys.begin());
fen.add(lower_bound(ys.begin(), ys.end(), y) - ys.begin(), +1);
}
if (type == 1) {
fen.add(lower_bound(ys.begin(), ys.end(), y) - ys.begin(), -1);
}
}
return res;
};
long long dist = [&]() -> long long {
long long l = 0, r = (long long)4e9 + 12345;
while (l < r) {
long long m = (l + r) >> 1;
if (countPair(m) >= k) {
r = m;
} else {
l = m + 1;
}
}
return l;
}();
for (long long x : [&]() -> vector<long long> {
vector<array<long long, 4>> events; // {x, erase:1 insert:0, y}
for (auto [x, y] : a) {
events.push_back({x, 0, x, y});
events.push_back({x + (dist - 1), 1, x, y});
}
sort(events.begin(), events.end());
set<array<long long, 2>> st;
vector<long long> res;
for (auto [t, type, x, y] : events) {
if (type == 0) {
auto it = st.lower_bound(array<long long, 2>{y - (dist - 1), -INF});
while (it != st.end() && (*it)[0] <= y + (dist - 1)) {
long long d = max(abs(y - (*it)[0]), abs(x - (*it)[1]));
res.push_back(d);
it++;
}
st.insert({y, x});
}
if (type == 1) {
st.erase(st.lower_bound(array<long long, 2>{y, x}));
}
}
assert(res.size() < k);
while (res.size() < k) res.push_back(dist);
sort(res.begin(), res.end());
return res;
}()) {
cout << x << '\n';
}
}
