#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 251000;
int n, k;
array<int, 2> pt[N];
vector<array<int, 2>> tt;
int get(int i, int j) {
return max(abs(pt[i][0] - pt[j][0]), abs(pt[i][1] - pt[j][1]));
}
void solve(int dist) {
tt.clear();
if (dist < 1) return;
set<array<int, 2>> st;
int ptr = 1;
for (int i = 1; i <= n && (int) tt.size() < k; i++) {
auto [x, y] = pt[i];
while (pt[ptr][0] < x - dist) {
st.erase({pt[ptr][1], ptr});
ptr++;
}
auto it = st.lower_bound({y - dist, 1});
while ((int) tt.size() < k && it != st.end() && (*it)[0] <= y + dist) {
tt.push_back({i, (*it)[1]});
it++;
}
st.insert({y, i});
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> pt[i][0] >> pt[i][1];
for (int i = 1; i <= n; i++) {
auto [x, y] = pt[i];
pt[i][0] = x + y;
pt[i][1] = x - y;
}
sort(pt + 1, pt + 1 + n);
int l = 1, r = (int)(4e9);
while (l < r) {
int mid = (l + r) / 2;
solve(mid);
assert((int) tt.size() <= k);
if ((int) tt.size() == k) r = mid;
else l = mid + 1;
}
solve(l - 1);
vector<array<int, 2>> cc = tt;
assert((int) cc.size() < k);
solve(l);
assert((int) tt.size() == k);
for (int i = 0; i < k && (int) cc.size() < k; i++)
if (get(tt[i][0], tt[i][1]) == l)
cc.push_back(tt[i]);
assert((int) cc.size() == k);
sort(begin(cc), end(cc), [&](auto a, auto b) {
return get(a[0], a[1]) < get(b[0], b[1]);
});
for (int i = 0; i < k; i++)
cout << get(cc[i][0], cc[i][1]) << '\n';
}
