#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 2.5e5, LIM = 2e9, inf = 1e18;
int N, K, x[NM+5], y[NM+5], pos_x[NM+5], pos_y[NM+5];
vector <int> arr_x, arr_y;
vector <int> upd[NM+5];
vector <pair <pii, int> > qry[NM+5];
int bit[NM+5];
set <pii> S;
set <pii>::iterator it;
vector <int> od, dlist;
void update(int p){
while (p <= N){
bit[p]++;
p += p & (-p);
}
}
int get(int p){
int res = 0;
while (p > 0){
res += bit[p];
p -= p & (-p);
}
return res;
}
bool check(int d){
for (int i = 1; i <= N; i++){
qry[i].clear();
bit[i] = 0;
}
for (int i = 1; i <= N; i++){
int lx = lower_bound(arr_x.begin(), arr_x.end(), x[i]-y[i]-d)-arr_x.begin()+1,
rx = upper_bound(arr_x.begin(), arr_x.end(), x[i]-y[i]+d)-arr_x.begin();
int ly = lower_bound(arr_y.begin(), arr_y.end(), x[i]+y[i]-d)-arr_y.begin()+1,
ry = upper_bound(arr_y.begin(), arr_y.end(), x[i]+y[i]+d)-arr_y.begin();
qry[rx].push_back(mp(mp(ly, ry), 1));
qry[lx-1].push_back(mp(mp(ly, ry), -1));
}
int sum = 0;
for (int i = 1; i <= N; i++){
for (int u : upd[i]) update(u);
for (pair <pii, int> q : qry[i])
sum += q.se*(get(q.fi.se)-get(q.fi.fi-1));
}
return sum-N >= 2*K;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++){
cin >> x[i] >> y[i];
arr_x.push_back(x[i]-y[i]);
arr_y.push_back(x[i]+y[i]);
}
sort(arr_x.begin(), arr_x.end()); arr_x.erase(unique(arr_x.begin(), arr_x.end()), arr_x.end());
sort(arr_y.begin(), arr_y.end()); arr_y.erase(unique(arr_y.begin(), arr_y.end()), arr_y.end());
for (int i = 1; i <= N; i++){
pos_x[i] = lower_bound(arr_x.begin(), arr_x.end(), x[i]-y[i])-arr_x.begin()+1;
pos_y[i] = lower_bound(arr_y.begin(), arr_y.end(), x[i]+y[i])-arr_y.begin()+1;
upd[pos_x[i]].push_back(pos_y[i]);
}
int l = 0, r = LIM-1, res = LIM;
while (l <= r){
int mid = l+(r-l)/2;
if (check(mid)){
res = mid;
r = mid-1;
}
else l = mid+1;
}
for (int i = 1; i <= N; i++) od.push_back(i);
sort(od.begin(), od.end(), [&](int i, int j){
return mp(x[i], y[i]) < mp(x[j], y[j]);
});
for (int i : od){
pii cur = mp(y[i]-res, -inf);
while (true){
it = S.upper_bound(cur);
if (it == S.end() || it->fi > y[i]+res) break;
if (it->se < x[i]-res){
S.erase(it);
continue;
}
dlist.push_back(abs(x[i] - it->se) + abs(y[i] - it->fi));
cur = *it;
}
S.insert(mp(y[i], x[i]));
}
sort(dlist.begin(), dlist.end());
for (int i = 0; i < K; i++)
cout << dlist[i] << '\n';
return 0;
}
