#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int MAXN = 2.5e5+10;
struct FT {
int n, bit[MAXN];
void init(int _n){ n = _n+1; memset(bit, 0, sizeof(bit)); }
int qry(int idx) { int ret = 0; for (++idx; idx > 0; idx -= idx & -idx) ret += bit[idx]; return ret; }
int qry(int l, int r) { return qry(r) - qry(l - 1); }
void upd(int idx, int delta) { for (++idx; idx < n; idx += idx & -idx) bit[idx] += delta; }
} ft;
string to_str(ar<ll, 2> a){ return "(" + to_string(a[0]) + ", " + to_string(a[1]) + ")"; }
ll dist(ar<ll, 2> a, ar<ll, 2> b){
return abs<ll>(a[0]-b[0]) + abs<ll>(a[1]-b[1]);
}
int n, k;
ar<ll, 2> a[MAXN], oa[MAXN];
ar<ll, 3> b[MAXN];
int cmp[MAXN];
map<ll, int> mp;
int main(){
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1], b[i][0] = a[i][0]+a[i][1], b[i][1] = a[i][0]-a[i][1], b[i][2] = i;
oa[i] = a[i];
}
sort(a, a+n), sort(b, b+n);
for (int i = 0; i < n; i++) mp[b[i][1]]++;
int cc=0;
for (auto& it : mp) it.second=cc++;
for (int i = 0; i < n; i++) cmp[i] = mp[b[i][1]];
auto cnt = [&](ll x) -> ll { //rotate 90 degrees, now want to find the point in some square
ft.init(n);
ll ans=0;
for (int i=0, j=i; i < n; i++){
for (; j < n && b[j][0]-b[i][0] <= x; j++)
ft.upd(cmp[j], 1);
const ll cl = b[i][1]-x, cr = b[i][1]+x;
auto rit = mp.upper_bound(cr);
if (rit != mp.begin()){
rit = prev(rit);
auto lit = mp.lower_bound(cl);
if (lit != mp.end()){
ans += ft.qry(lit->second, rit->second);
}
}
if (ans-(i+1) >= k) return ans-(i+1);
ft.upd(cmp[i], -1);
}
return ans-n;
};
ll lo=-1, hi=1e18+10, mid=(lo+hi)/2;
while (lo < mid && mid < hi) {
if (cnt(mid) >= k) hi = mid;
else lo = mid;
mid = (lo+hi)/2;
}
vector<ll> ans{hi}; ans.reserve(k);
set<pair<ll, int>> s;
ll x=hi-1;
for (int i=0, j=i; i < n; i++){
assert(j >= i);
for (; j < n && b[j][0]-b[i][0] <= x; j++)
s.insert({b[j][1], j});
s.erase(s.find({b[i][1], i}));
ll cl = b[i][1]-x, cr = b[i][1]+x;
auto lit = s.lower_bound({cl, -1});
while (lit != s.end() && lit->first <= cr) {
int cv = lit->second;
ll d = dist(oa[b[i][2]], oa[b[cv][2]]);
//cerr << i << ' ' << cv << ' ' << to_str(b[i]) << ' ' << to_str(b[cv]) << endl;
ans.push_back(d);
lit = next(lit);
}
}
sort(ans.begin(), ans.end());
while (sz(ans) < k) ans.push_back(ans.back());
for (auto& it : ans) cout << it << '\n';
}
