#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n , K;
cin >> n >> K;
vector<int> x(n + 1) , y(n + 1);
for(int i = 1;i <= n;i ++){
cin >> x[i] >> y[i];
}
auto nx = x , ny = y;
vector<int> o(n + 1);
iota(o.begin() , o.end() , 0);
sort(o.begin() + 1 , o.end() , [&](int i , int j){
return pair<int , int>{x[i] , y[i]} < pair<int , int>{x[j] , y[j]};
});
for(int i = 1;i <= n;i ++){
x[i] = nx[o[i]];
y[i] = ny[o[i]];
}
vector<int> f(2 * n + 1);
auto upd = [&](int x , int w){
while(x <= 2 * n){
f[x] += w;
x += x&-x;
}
};
auto query = [&](int x){
int s = 0;
while(x > 0){
s += f[x];
x -= x&-x;
}
return s;
};
function<int(int , int , int)> solve = [&](int l , int r , int C){
if(l >= r){
return 0;
}
int m = (l + r) / 2;
vector<int> e(r - l + 1);
iota(e.begin() , e.end() , l);
sort(e.begin() , e.end() , [&](int i , int j){
return pair<int , int>{y[i] , x[i]} < pair<int , int>{y[j] , x[j]};
});
//(x[i] + y[i]) - (x[j] + y[j]) <= C
//(x[i] - y[i]) - (x[j] - y[j]) <= C
vector<int> values;
for(int i = l;i <= r;i ++){
int t = x[i] + y[i];
values.emplace_back(t);
values.emplace_back(t - C);
}
sort(values.begin() , values.end());
map<int , int> M;
for(int i = 0;i < (int)values.size();i ++){
M[values[i]] = (i > 0 ? M[values[i - 1]] + (values[i] != values[i - 1]) : 1);
}
int cnt = 0;
for(int i : e){
int t = x[i] + y[i];
if(i > m){
cnt += query(2 * n) - query(M[t - C] - 1);
}else{
upd(M[t] , +1);
}
}
for(int i = l;i <= m;i ++){
upd(M[x[i] + y[i]] , -1);
}
M.clear();
vector<int>().swap(values);
for(int i = l;i <= r;i ++){
int t = x[i] - y[i];
values.emplace_back(t);
values.emplace_back(t - C);
}
sort(values.begin() , values.end());
for(int i = 0;i < (int)values.size();i ++){
M[values[i]] = (i > 0 ? M[values[i - 1]] + (values[i] != values[i - 1]) : 1);
}
reverse(e.begin() , e.end());
for(int i : e){
int t = x[i] - y[i];
if(i > m){
cnt += query(2 * n) - query(M[t - C] - 1);
}else{
upd(M[t] , +1);
}
}
for(int i = l;i <= m;i ++){
upd(M[x[i] - y[i]] , -1);
}
return cnt + solve(l , m , C) + solve(m + 1 , r , C);
};
int ans = 0;
for(int bit = 24;bit >= 0;bit --){
ans += 1 << bit;
int cnt = solve(1 , n , ans);
if(cnt >= K){
ans -= 1 << bit;
}
}
vector<int> v;
//!
function<void(int , int)> solve_dists = [&](int l , int r){
if(l >= r){
return;
}
int m = (l + r) / 2;
vector<int> e(r - l + 1);
iota(e.begin() , e.end() , l);
sort(e.begin() , e.end() , [&](int i , int j){
return pair<int , int>{y[i] , x[i]} < pair<int , int>{y[j] , x[j]};
});
//(x[i] + y[i]) - (x[j] + y[j]) <= C
//(x[i] - y[i]) - (x[j] - y[j]) <= C
multiset<int> S;
S.insert(-2E9 - 10);
for(int i : e){
int t = x[i] + y[i];
if(i > m){
if(!S.empty()){
auto it = --S.end();
while(t - *it <= ans){
v.emplace_back(t - *it);
--it;
}
}
}else{
S.insert(t);
}
}
S.clear();
reverse(e.begin() , e.end());
S.insert(-2E9 - 10);
for(int i : e){
int t = x[i] - y[i];
if(i > m){
if(!S.empty()){
auto it = --S.end();
while(t - *it <= ans){
v.emplace_back(t - *it);
--it;
}
}
}else{
S.insert(t);
}
}
solve_dists(l , m);
solve_dists(m + 1 , r);
};
solve_dists(1 , n);
++ans;
sort(v.begin() , v.end());
while((int)v.size() < K){
v.emplace_back(ans);
}
for(int x : v){
cout << x << " ";
}
cout << '\n';
}
