#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=250010, INF=4e9;
int n, k, x[N], y[N], v1=INF+1, v2=INF+1;
array<int, 2> a[N];
vector<int> vec1, vec2;
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 s, int e, int t) {
if(s>=e) return 0;
int m=(s+e)/2, ret=0;
vector<int> com;
vector<array<int, 2>> vl, vr;
for(int i=s; i<=m; i++) com.push_back(x[i]+y[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(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
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]) T.update(lower_bound(com.begin(), com.end(), vl[j][1])-com.begin()+1), j++;
ret+=T.query(lower_bound(com.begin(), com.end(), vr[i][1]-t)-com.begin()+1, com.size());
}
T.clear();
return ret+f(s, m, t)+f(m+1, e, t);
}
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) vec1.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);
}
int f2(int s, int e, int t) {
if(s>=e) return 0;
int m=(s+e)/2, ret=0;
vector<int> com;
vector<array<int, 2>> vl, vr;
for(int i=s; i<=m; i++) com.push_back(x[i]-y[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(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
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]) T.update(lower_bound(com.begin(), com.end(), vl[j][1])-com.begin()+1), j++;
ret+=T.query(lower_bound(com.begin(), com.end(), vr[i][1]-t)-com.begin()+1, com.size());
}
T.clear();
return ret+f2(s, m, t)+f2(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) vec2.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];
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(1, n, m)>=k) v1=m, e=m-1;
else s=m+1;
}
g(1, n, v1-1);
if(v1<=INF) while(vec1.size()<k) vec1.push_back(v1);
for(int s=0, e=INF; s<=e; ) {
int m=(s+e)/2;
if(f2(1, n, m)>=k) v2=m, e=m-1;
else s=m+1;
}
g2(1, n, v2-1);
if(v2<=INF) while(vec2.size()<k) vec2.push_back(v2);
for(int i:vec2) vec1.push_back(i);
sort(vec1.begin(), vec1.end());
for(int i=0; i<k; i++) cout<<vec1[i]<<"\n";
return 0;
}
