#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 250005;
int n, k;
long long x[maxn], y[maxn];
int vx[maxn], vy[maxn];
vector<long long> vec;
int ord[maxn];
int bit[maxn];
void update(int i, int val) {
for(; i <= n; i += i & (-i)) {
bit[i] += val;
}
}
int get(int i) {
int ans = 0;
for(; i > 0; i -= i & (-i)) {
ans += bit[i];
}
return ans;
}
bool check(long long mid) {
long long res = 0;
memset(bit, 0, sizeof(bit));
int ptr = 1;
for(int i = 1; i <= n; ++i) {
while(ptr < i and x[ord[i]] - x[ord[ptr]] > mid) {
update(vy[ord[ptr]], -1);
++ptr;
}
int p1 = upper_bound(vec.begin(), vec.end(), y[ord[i]] + mid) - vec.begin();
int p2 = lower_bound(vec.begin(), vec.end(), y[ord[i]] - mid) - vec.begin();
res += get(p1) - get(p2);
update(vy[ord[i]], 1);
}
return res >= k;
}
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
int a, b; cin >> a >> b;
x[i] = a + b, y[i] = a - b;
vec.push_back(y[i]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int i = 1; i <= n; ++i) {
vy[i] = lower_bound(vec.begin(), vec.end(), y[i]) - vec.begin() + 1;
}
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [](const int &a, const int &b) -> bool {
return x[a] < x[b];
});
long long l = 0, r = 4e9, res = 4e9;
while(l <= r) {
long long mid = (l + r) >> 1;
if(check(mid)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
int ptr = 1;
set<pair<long long, int>> s;
vector<long long> cand;
for(int i = 1; i <= n; ++i) {
while(ptr < i and x[ord[i]] - x[ord[ptr]] >= res) {
s.erase(s.find(make_pair(y[ord[ptr]], ord[ptr])));
++ptr;
}
auto t1 = s.upper_bound(make_pair(y[ord[i]] + res - 1, n + 1));
auto t = s.lower_bound(make_pair(y[ord[i]] - res + 1, -1));
while(t != t1) {
int id = t->second;
cand.push_back(max(abs(x[ord[i]] - x[id]), abs(y[ord[i]] - y[id])));
t++;
}
s.insert(make_pair(y[ord[i]], ord[i]));
}
sort(cand.begin(), cand.end());
debug(cand);
while((int)cand.size() < k) {
cand.push_back(res);
}
for(auto i:cand) {
cout << i << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
/*
5 10
1 -1
2 0
-1 0
0 2
0 -2
*/
