#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 250003;
vector<ll> cmpSum, cmpDiff;
pl a[mn];
ll n;
struct BIT {
vector<int> tr;
BIT (int sz) : tr(sz + 1) {}
int p (int k) { return k & -k; }
void update (int k, int val) {
for (; k < tr.size(); k += p(k)) tr[k] += val;
}
int preSum (int k, int ans = 0) {
for (; k; k -= p(k)) ans += tr[k];
return ans;
}
void refresh() { fill(all(tr), 0); }
} treeSum(mn), treeDiff(mn);
int getSum (ll targ) {
return lower_bound(all(cmpSum), targ) - cmpSum.begin() + 1;
}
int getDiff (ll targ) {
return lower_bound(all(cmpDiff), targ) - cmpDiff.begin() + 1;
}
int pointSum (int i) {
ll x, y; tie(x, y) = a[i];
return lower_bound(all(cmpSum), x + y) - cmpSum.begin() + 1;
}
int pointDiff (int i) {
ll x, y; tie(x, y) = a[i];
return lower_bound(all(cmpDiff), x - y) - cmpDiff.begin() + 1;
}
ll countClose (ll ub) {
ll cnt = 0;
treeSum.refresh(), treeDiff.refresh();
for (int L = 0, R = 0; R < n; R++) {
treeSum.update(pointSum(R), 1);
treeDiff.update(pointDiff(R), 1);
while (a[R].first - a[L].first > ub) {
treeSum.update(pointSum(L), -1);
treeDiff.update(pointDiff(L), -1);
L++;
}
cnt += L;
ll x, y; tie(x, y) = a[R];
cnt += treeSum.preSum(getSum(x + y - ub) - 1);
cnt += treeDiff.preSum(getDiff(x - y - ub) - 1);
}
return n * (n - 1) / 2 - cnt;
}
ll distance (ll x, ll y, ll i, ll j) {
return abs(x - i) + abs(y - j);
}
void getPoints (ll ub, ll k, vector<ll> &ans) {
set<pl> s;
for (int L = 0, R = 0; R < n; R++) {
ll x, y; tie(x, y) = a[R];
s.emplace(y, x);
while (a[R].first - a[L].first > ub) {
ll x, y; tie(x, y) = a[L++];
s.erase(make_pair(y, x));
}
for (auto it = s.lower_bound(make_pair(y - ub, 0)); it != s.end() && it->first <= y + ub; it++) {
ll cur = distance(it->second, it->first, x, y);
if (0 < cur && cur <= ub) ans.push_back(cur);
if (ans.size() == k) break;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll k; cin >> n >> k;
for (int i = 0; i < n; i++) {
ll x, y; cin >> x >> y;
cmpSum.push_back(x + y), cmpDiff.push_back(x - y);
a[i] = {x, y};
}
sort(a, a + n), sort(all(cmpSum)), sort(all(cmpDiff));
filter(cmpSum), filter(cmpDiff);
ll ans = 0, save = 0;
for (ll mask = 1LL << 31; mask > 0; mask >>= 1) {
ll cur = countClose(ans | mask);
if (cur < k) ans |= mask, save = cur;
}
vector<ll> vec;
getPoints(ans, save, vec);
sort(all(vec));
for (ll u : vec) cout << u << "\n";
for (int i = 0; i < k - save; i++) cout << ans + 1 << "\n";
return 0;
}
