#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set __gnu_pbds::tree<array<long long, 2>, __gnu_pbds::null_type, less<array<long long, 2>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>
const long long INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<array<int, 2>> a(n);
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};
}
auto countPair = [](vector<array<int, 2>> 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());
ordered_set st;
long long res = 0;
for (auto [t, type, x, y] : events) {
if (type == 0) {
res += st.order_of_key(array<long long, 2>{y + dist, +INF}) - st.order_of_key(array<long long, 2>{y - dist, -INF});
st.insert(array<long long, 2>{y, x});
}
if (type == 1) {
st.erase(st.lower_bound({y, x}));
}
}
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(a, 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());
ordered_set 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';
}
}
