#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
a[i] = make_pair(x + y, y - x); // rotate 45 degress
}
sort(a.begin(), a.end());
long long lo = 0, hi = 4e9;
while (lo < hi) {
long long mid = (lo + hi) / 2;
int p = 0, cnt = 0;
multiset<int> se;
for (int i = 0; i < n && cnt < k; ++i) {
auto [x, y] = a[i];
while (p < i && (long long) x - a[p].first > mid) {
se.erase(se.find(a[p].second));
p++;
}
auto it = se.lower_bound(y - mid);
while (it != se.end()) {
int yy = *it;
if ((long long) yy - y > mid) {
break;
} else {
cnt++;
it++;
}
}
se.insert(y);
}
if (cnt >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
vector<long long> ans;
multiset<pair<long long, int>> se;
for (int i = 0, p = 0; i < n; ++i) {
auto [x, y] = a[i];
while (p < i && (long long) x - a[p].first >= hi) {
se.erase(se.find({a[p].second, a[p].first}));
p++;
}
pair<long long, int> key = {(long long) y - hi, INT_MAX};
auto it = se.lower_bound(key);
while (it != se.end()) {
auto [yy, xx] = *it;
if ((long long) yy - y >= hi) {
break;
} else {
ans.push_back(max(llabs((long long) y - yy), (long long) x - xx));
it++;
}
}
se.emplace(y, x);
}
sort(ans.begin(), ans.end());
while ((int) ans.size() < k) {
ans.push_back(hi);
}
for (int i = 0; i < k; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
