#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define endl '\n'
#define all(x) x.begin(),x.end()
const int N = 3e5;
int n, k;
int cnt[N], fen[N], L[N], R[N];
pair<int,int> nums[N];
vector<int> YS, got;
deque<int> tree[4*N];
vector<pair<int,int>> ans;
void PUSH(int v,int tl,int tr,int ind,int x) {
if (tr < ind || tl > ind) return;
tree[v].push_back(x);
if (tl == tr) return;
int mid = (tl+tr)/2;
PUSH(2*v,tl,mid,ind,x);
PUSH(2*v+1,mid+1,tr,ind,x);
}
void REM(int v,int tl,int tr,int ind) {
if (tr < ind || tl > ind) return;
tree[v].pop_front();
if (tl == tr) return;
int mid = (tl+tr)/2;
REM(2*v,tl,mid,ind);
REM(2*v+1,mid+1,tr,ind);
}
void GRAB(int v,int tl,int tr,int l,int r) {
if (r < l) return;
if (tl == l && tr == r) {
for (int val : tree[v]) {
got.push_back(val);
}
return;
}
int mid = (tl+tr)/2;
GRAB(2*v,tl,mid,l,min(r,mid));
GRAB(2*v+1,mid+1,tr,max(l,mid+1),r);
}
void SET(int i,int x) {
int y = x;
x = x-cnt[i];
cnt[i] = y;
while (i < N) {
fen[i] += x;
i |= (i+1);
}
}
int PREF(int r) {
int ans = 0;
while (r >= 0) {
ans += fen[r];
r = (r&(r+1))-1;
}
return ans;
}
int SUM(int l,int r) {
return PREF(r)-PREF(l-1);
}
bool F(int a) {
int l = 0;
int r = 0;
for (int i = 0;i < YS.size();i++) {
while (YS[i]-YS[l] > a) {
l++;
}
while (r+1 < YS.size() && YS[r+1]-YS[i] <= a) {
r++;
}
L[i] = l;
R[i] = r;
}
for (int i = 0;i < YS.size();i++) {
SET(i,0);
}
l = 1;
int sm = 0;
for (int i = 1;i <= n;i++) {
while (nums[i].first-nums[l].first > a) {
int compy = lower_bound(all(YS),nums[l].second)-YS.begin();
SET(compy,cnt[compy]-1);
l++;
}
int compy = lower_bound(all(YS),nums[i].second)-YS.begin();
sm += SUM(L[compy],R[compy]);
SET(compy,cnt[compy]+1);
}
return sm >= k;
}
void FIND(int a) {
int l = 0;
int r = 0;
for (int i = 0;i < YS.size();i++) {
while (YS[i]-YS[l] > a) {
l++;
}
while (r+1 < YS.size() && YS[r+1]-YS[i] <= a) {
r++;
}
L[i] = l;
R[i] = r;
}
l = 1;
for (int i = 1;i <= n;i++) {
while (nums[i].first-nums[l].first > a) {
int compy = lower_bound(all(YS),nums[l].second)-YS.begin();
REM(1,0,YS.size()-1,compy);
l++;
}
int compy = lower_bound(all(YS),nums[i].second)-YS.begin();
got.clear();
GRAB(1,0,YS.size()-1,L[compy],R[compy]);
for (int val : got) {
ans.push_back({val,i});
}
PUSH(1,0,YS.size()-1,compy,i);
}
}
int dis(int i,int j){
return max(abs(nums[i].first-nums[j].first),abs(nums[i].second-nums[j].second));
}
bool cmp(pair<int,int> a,pair<int,int> b) {
return (dis(a.first,a.second)<dis(b.first,b.second));
}
void solve() {
cin >> n >> k;
for (int i = 1;i <= n;i++) {
cin >> nums[i].first >> nums[i].second;
nums[i] = {nums[i].first+nums[i].second,nums[i].second-nums[i].first};
}
sort(nums+1,nums+n+1);
for (int i = 1;i <= n;i++) {
YS.push_back(nums[i].second);
}
sort(all(YS));
YS.resize(unique(all(YS))-YS.begin());
int l = 0;
int r = 2e9;
while (r-l > 1) {
int mid = (l+r)/2;
if (F(mid)) {
r = mid;
} else {
l = mid;
}
}
FIND(r);
sort(all(ans),cmp);
for (auto val : ans) {
cout << dis(val.first,val.second) << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
}
