#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())
const int MXN = 250005;
int n, k;
pii a[MXN];
vector<ll> cmp;
inline int GI(ll x) { return lower_bound(all(cmp), x)-cmp.begin(); }
int N;
int fen[MXN];
set<pii> st;
inline void build() {
fill(fen+1, fen+N+1, 0);
st.clear();
}
inline void upd(int p, int x, int y) {
if(x==1) st.insert({p, y});
else st.erase({p, y});
for(++p; p<=N; p+=p&-p) fen[p] += x;
}
inline pii get(int s, int e) {
int res=0;
int S=s;
for(; e; e-=e&-e) res += fen[e];
for(; s; s-=s&-s) res -= fen[s];
if(!res) return {0, 0};
return {res, st.lower_bound({S, 0})->Y};
}
ll check(ll m) {
build();
ll res = 0;
int p=1;
for(int i=1; i<=n; i++) {
while(a[i].X+a[i].Y - (a[p].X+a[p].Y) > m) {
upd(GI(a[p].X-a[p].Y), -1, p);
p++;
}
res += get(GI(a[i].X-a[i].Y-m), GI(a[i].X-a[i].Y+m+1)).X;
upd(GI(a[i].X-a[i].Y), 1, i);
}
return res;
}
int wh[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i].X >> a[i].Y, cmp.push_back(a[i].X-a[i].Y);
sort(a+1, a+n+1, [&](pii x, pii y) {
return x.X+x.Y < y.X+y.Y;
});
sort(all(cmp));
cmp.resize(unique(all(cmp))-cmp.begin());
N = SZ(cmp);
for(int i=1; i<=n; i++) wh[i] = GI(a[i].X-a[i].Y);
ll l=0, r=4e9;
while(r-l>1)
(check(mid)>=k ? r : l) = mid;
int c = k-check(l);
build();
vector<ll> ans;
for(int i=0; i<c; i++) ans.push_back(r);
int p=1;
for(int i=1; i<=n; i++) {
while(a[i].X+a[i].Y - (a[p].X+a[p].Y) > l) {
upd(wh[p], -1, p);
p++;
}
vector<int> vec = {i};
while(1) {
pii x = get(GI(a[i].X-a[i].Y-l), GI(a[i].X-a[i].Y+l+1));
if(!x.X) break;
ans.push_back(1ll*abs(a[i].X-a[x.Y].X) + abs(a[i].Y-a[x.Y].Y));
upd(wh[x.Y], -1, x.Y);
vec.push_back(x.Y);
}
for(int j : vec)
upd(wh[j], 1, j);
}
sort(all(ans));
for(ll i : ans) cout << i << '\n';
return 0;
}
