#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
#define N 250020
int n, k;
pii w[N];
int bit[N],ans[N];
inline void upd(int x, int v){
x+=4;
assert(x>0);
for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
inline int qry(int x){
x+=4;
assert(x>0);
int sum = 0;
for(int i = x;i>0;i-=(i&-i)) sum+=bit[i];
return sum;
}
vector<ll> compress;
int compy[N], pilhax[N], pilhay[N], pilhaid[N];
deque<int>tree[4*N];
#define m ((a+b)/2)
void updd(int nod, int a, int b, int i, int j,bool add){
if(add) tree[nod].pb(j);
else tree[nod].pop_front();
if(a==b) return;
if(i <= m) updd(2*nod,a,m,i,j,add);
else updd(2*nod+1,m+1,b,i,j,add);
}
void get(int nod, int a, int b, int i, int j, vector<int>&curr){
if(j < a or i > b) return;
if(i <= a and j >= b){
for(auto x: tree[nod]){
curr.pb(x);
}
return;
}
get(2*nod, a, m, i, j, curr);get(2*nod+1,m+1,b,i,j,curr);
}
inline int check(int mid){
for(int i = 0; i <= n+10;i++) bit[i]=0;
int l=0,r=-1, cost=0;
for(int i=1;i<=n;i++){
int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
while(l <= r and pilhax[l] < w[i].f-mid){
upd(pilhay[l], -1);
l++;
}
if(mn <= mx) cost+=qry(mx)-qry(mn-1);
if(cost>=k)return cost;
r++;
pilhax[r] = w[i].f;//({w[i].f, compy[i]});
pilhay[r] = compy[i];
upd(compy[i], 1);
}
return cost;
}
inline void take(int mid, vector<int>&ans){
int l=0,r=-1, cost=0;
for(int i=1;i<=n;i++){
while(l <= r and pilhax[l] < w[i].f-mid){
updd(1,1,n,pilhay[l], pilhaid[l], 0);
l++;
}
int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
vector<int>curr;
get(1,1,n,mn,mx, curr);
for(auto x: curr){
int dx = abs(w[i].f - w[x].f), dy = abs(w[i].s - w[x].s);
ans.pb(max(dx,dy));
}
r++;
pilhax[r] = w[i].f;//({w[i].f, compy[i]});
pilhay[r] = compy[i];
pilhaid[r] = i;
updd(1,1,n,pilhay[r], pilhaid[r], 1);
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k;
for(int i = 1, x, y; i <= n; i++){
cin>>x>>y;
w[i]={x+y,x-y};
compress.push_back(x-y);
}
sort(w+1,w+n+1);
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(),compress.end()),compress.end());
for(int i = 1; i<=n;i++)compy[i] = (upper_bound(compress.begin(), compress.end(), w[i].s)-compress.begin());
int ini = 0, fim = (int)(4e9), mid, best=-1;
while(fim>=ini){
mid=(ini+fim)/2;
if(check(mid) >= k) best=mid,fim=mid-1;
else ini=mid+1;
}
vector<int> ans;
int S = check(best - 1);
for(int i = 0; i < k-S; i++) ans.pb(best);
take(best-1,ans);
sort(all(ans));
for(int i=0;i<sz(ans);i++)cout<<ans[i]<<"\n";
}
