#include <algorithm>
#include <bits/stdc++.h>
#include <ios>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)
struct Fenwick{
vector<int> tr;
ll offs, n;
Fenwick(ll N){
n=N+20; offs=10;
tr.resize(n+1);
}
void add(ll _i, ll x){
_i+=offs; for (ll i=_i; i<=n; i+=(-i&i)){
tr[i]+=x;
}
}
ll get(ll _i){
ll sum=0; _i+=offs;
for (ll i=_i; i; i-=(-i&i)){
sum+=tr[i];
}
return sum;
}
void clear(){
tr.assign(n+1, 0);
}
};
struct FenwickSick{
vector<multiset<ll>> tr;
ll n, offs;
FenwickSick(ll N){
n=N+20; offs=10;
tr.resize(n+1);
}
void add(ll i, ll x){
i+=offs; for (; i<=n; i+=(-i&i)){
tr[i].insert(x);
}
}
void collect(ll i, ll lim, vector<ll> &col){
i+=offs; for (; i; i-=(-i&i)){
if (tr[i].empty()) continue;
auto iter = tr[i].upper_bound(lim);
if (iter!=tr[i].begin()){
do{
iter--;
col.push_back(*iter);
}while (iter!=tr[i].begin());
}
}
}
};
void solve(){
ll n, k; cin >> n >> k;
vector<pair<ll, ll>> pts(n);
vector<pair<ll, ll>> dpts(n);
vector<ll> dxs, dys;
for (ll i=0; i<n; i++){
cin >> pts[i].ff >> pts[i].ss;
dpts[i] = {pts[i].ff+pts[i].ss, pts[i].ff-pts[i].ss};
// dxs.push_back(dpts[i].ff);
dys.push_back(dpts[i].ss);
}
// sort(dxs.begin(), dxs.end()); dxs.erase(unique(dxs.begin(), dxs.end()), dxs.end());
sort(dys.begin(), dys.end()); dys.erase(unique(dys.begin(), dys.end()), dys.end());
sort(dpts.begin(), dpts.end());
ll l=0, r=1e10, dcnt=0;
Fenwick tr(dys.size());
while(l+1<r){
ll mid = (l+r)/2, cnt=0;
ll lo=0, hi=-1; tr.clear();
for (ll i=0; i<n; i++){
while (dpts[lo].ff<dpts[i].ff-mid) {
ll ind = lower_bound(dys.begin(), dys.end(), dpts[lo].ss)-dys.begin();
tr.add(ind, -1); lo++;
}
while (hi+1<n and dpts[hi+1].ff<=dpts[i].ff+mid){
hi++; ll ind = lower_bound(dys.begin(), dys.end(), dpts[hi].ss)-dys.begin();
tr.add(ind, 1);
}
ll uind = upper_bound(dys.begin(), dys.end(), dpts[i].ss+mid)-dys.begin()-1;
ll lind = lower_bound(dys.begin(), dys.end(), dpts[i].ss-mid)-dys.begin()-1;
cnt+=tr.get(uind)-tr.get(lind)-1;
}
if (cnt/2<=k) {
l=mid; dcnt=cnt/2;
} else r=mid;
}
vector<ll> res;
for (ll i=dcnt; i<k; i++) res.push_back(l+1);
map<ll, vector<ll>> sweep;
vector<ll> sys;
for (auto [x, y]:pts){
sweep[x].push_back(y);
sys.push_back(y);
sys.push_back(-y);
sys.push_back(-y-1);
}
sort(sys.begin(), sys.end()); sys.erase(unique(sys.begin(), sys.end()), sys.end());
FenwickSick trs(sys.size()), trb(sys.size());
vector<ll> add;
for (auto &[x, ys]:sweep){
sort(ys.begin(), ys.end());
for (auto y:ys){
ll val = l-x-y; add.clear();
ll ind1 = lower_bound(sys.begin(), sys.end(), y)-sys.begin();
trs.collect(ind1, val, add);
for (auto ch:add) res.push_back(ch+x+y);
val = l-x+y; add.clear();
ind1 = lower_bound(sys.begin(), sys.end(), -y-1)-sys.begin();
trb.collect(ind1, val, add);
for (auto ch:add) res.push_back(ch+x-y);
}
for (ll i=0; i<(ll)ys.size(); i++){
for (ll j=i-1; j>=0 and ys[i]-ys[j]<=l; j--){
res.push_back(ys[i]-ys[j]);
}
}
for (auto y:ys){
ll ind1 = lower_bound(sys.begin(), sys.end(), y)-sys.begin();
trs.add(ind1, -x-y);
ind1 = lower_bound(sys.begin(), sys.end(), -y)-sys.begin();
trb.add(ind1, -x+y);
}
}
sort(res.begin(), res.end());
for (auto ch:res) cout << ch << ln;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef LOCAL
auto start = chrono::high_resolution_clock::now();
#endif
ll t=1;
// cin >> t;
for (ll __c=1; __c<=t; __c++) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}
