#include <bits/stdc++.h>
#include <ctime>
#include <random>
#define fu(i,a,b) for(int i = a; i < b; i++)
#define fd(i,a,b) for(int i = a; i >= b; i--)
#define pb push_back
#define ll long long
#define fi first
#define se second
#define bit(x,y) ((x >> y)&1)
#define MASK(x) (1 << x)
#define ALL(x) (x).begin(), (x).end()
#define vi pair<ll,ll>
#define vvl vector<vector<ll>>
#define vvvi pair<ll,pair<ll,pair<ll,ll>>>
#define HIGH_MIN(x,y) (a[x] > a[y] ? y : x)
using namespace std;
const ll MAXN = 5e5+2;
const ll MAXC = 1e6+5 ;
const ll base = 31;
const ll MOD = 1e9+7;
const ll LG = 20;
const ll BS = 548;
const ll dx[] = {0,1,0,-1};
const ll dy[] = {-1,0,1,0};
const ll inf = 2e9;
bool minimize(ll& a,const ll& b){ if(a > b){ a = b; return true; } else return false;}
bool maximize(ll& a,const ll& b){ if(a < b){ a = b; return true; } else return false;}
void add(ll& a,const ll& b){ a += b; if(a >= MOD) a -= MOD; }
ll sub(ll a,ll b){ ll r = a - b + MOD; if(r >= MOD) r -= MOD; return r;}
ll n,k,a[MAXN],b[MAXN];
vi c[MAXN];
vector<ll> ans;
ll dist(ll i,ll j){
return max(abs(c[i].fi-c[j].fi),abs(c[i].se-c[j].se));
}
ll check(ll x){
set<vi> st; ans.clear();
ll j = 1;
fu(i,1,n+1){
while(!st.empty() && c[j].fi < c[i].fi - x){
st.erase(make_pair(c[j].se,j));
j++;
}
auto it = st.upper_bound(make_pair(c[i].se-x,-inf));
while(it != st.end() && ans.size() < k && it->fi <= c[i].se + x){
ans.emplace_back(dist(i,it->se));
it = next(it);
}
if(ans.size() == k) break;
st.emplace(c[i].se,i);
}
return ans.size();
}
void solve(){
cin >> n >> k;
fu(i,1,n+1){
cin >> a[i] >> b[i];
c[i] = {a[i]+b[i],a[i]-b[i]};
}
sort(c+1,c+n+1);
ll l = 0, r = 10000000000,dd = -1;
while(l <= r){
ll mid = l+r >> 1;
// cout << l << ' ' << r << '\n';
if(check(mid) >= k){
dd = mid;
r = mid-1;
}
else l = mid+1;
}
check(dd);
// while(ans.size() < k) ans.push_back(dd+1);
sort(ALL(ans));
for(ll it: ans) cout << it << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("code.inp","r",stdin);
// freopen("code.out","w",stdout);
ll tt = 1;
while(tt--) solve();
return 0;
}
