#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=250010, INF=4e9;
int n, k, x[N], y[N], v=INF+1;
array<int, 2> a[N];
vector<int> com, vec;
class seg {
public:
void update(int k) {
vec.push_back(k);
for(int i=k; i<=n; i+=i&-i) tree[i]++;
}
int query(int k) {
int ret=0;
for(int i=k; i>=1; i-=i&-i) ret+=tree[i];
return ret;
}
int query(int l, int r) {return query(r)-query(l-1);}
void clear() {
for(int k:vec) {
for(int i=k; i<=n; i+=i&-i) tree[i]=0;
}
vec.clear();
}
private:
int tree[N];
vector<int> vec;
}T;
int f(int t) {
int ret=0;
vector<array<int, 3>> p;
for(int i=1; i<=n; i++) {
p.push_back({a[i][0]+a[i][1], INF, lower_bound(com.begin(), com.end(), a[i][0]-a[i][1])-com.begin()+1});
int l=lower_bound(com.begin(), com.end(), a[i][0]-a[i][1]-t)-com.begin()+1;
int r=lower_bound(com.begin(), com.end(), a[i][0]-a[i][1]+t+1)-com.begin();
p.push_back({a[i][0]+a[i][1]-t, l, -r}), p.push_back({a[i][0]+a[i][1]+t+1, l, r});
}
sort(p.begin(), p.end());
for(auto [x, l, r]:p) {
if(l==INF) T.update(r);
else if(l>0) ret+=T.query(l, r);
else ret-=T.query(-l, r);
}
T.clear();
return (ret-n)/2;
}
void g(int s, int e, int t) {
if(s>=e) return;
int m=(s+e)/2, ret=0;
priority_queue<int> pq;
vector<array<int, 2>> vl, vr;
for(int i=s; i<=m; i++) vl.push_back({y[i], x[i]+y[i]});
for(int i=m+1; i<=e; i++) vr.push_back({y[i], x[i]+y[i]});
sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());
for(int i=0, j=0; i<vr.size(); i++) {
while(j<vl.size() && vl[j][0]<=vr[i][0]) pq.push(vl[j][1]), j++;
vector<int> tmp;
while(!pq.empty() && pq.top()>=vr[i][1]-t) vec.push_back(vr[i][1]-pq.top()), tmp.push_back(pq.top()), pq.pop();
for(int t:tmp) pq.push(t);
}
g(s, m, t), g(m+1, e, t);
}
void g2(int s, int e, int t) {
if(s>=e) return;
int m=(s+e)/2, ret=0;
priority_queue<int> pq;
vector<array<int, 2>> vl, vr;
for(int i=s; i<=m; i++) vl.push_back({y[i], x[i]-y[i]});
for(int i=m+1; i<=e; i++) vr.push_back({y[i], x[i]-y[i]});
sort(vl.rbegin(), vl.rend()), sort(vr.rbegin(), vr.rend());
for(int i=0, j=0; i<vr.size(); i++) {
while(j<vl.size() && vl[j][0]>vr[i][0]) pq.push(vl[j][1]), j++;
vector<int> tmp;
while(!pq.empty() && pq.top()>=vr[i][1]-t) vec.push_back(vr[i][1]-pq.top()), tmp.push_back(pq.top()), pq.pop();
for(int t:tmp) pq.push(t);
}
g2(s, m, t), g2(m+1, e, t);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=1; i<=n; i++) cin>>a[i][0]>>a[i][1], com.push_back(a[i][0]-a[i][1]);
sort(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
sort(a+1, a+n+1);
for(int i=1; i<=n; i++) x[i]=a[i][0], y[i]=a[i][1];
for(int s=0, e=INF; s<=e; ) {
int m=(s+e)/2;
if(f(m)>=k) v=m, e=m-1;
else s=m+1;
}
g(1, n, v-1), g2(1, n, v-1);
while(vec.size()<k) vec.push_back(v);
sort(vec.begin(), vec.end());
for(int i=0; i<k; i++) cout<<vec[i]<<"\n";
return 0;
}
