#include<bits/stdc++.h>
#define LL long long
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]];
}
int left;
multiset<LL> S;
vector<int> v;
function<void(int , int , LL , int)> solve = [&](int l , int r , LL C , int g){
if(l >= r || left <= 0){
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
S.insert(-1E16 - 10);
for(int i : e){
LL t = x[i] + y[i];
if(i > m){
if(!S.empty()){
auto it = --S.end();
while(t - *it <= C && left > 0){
if(g){
v.emplace_back(t - *it);
}
--left;
--it;
}
}
}else{
S.insert(t);
}
}
S.clear();
reverse(e.begin() , e.end());
S.insert(-1E16 - 10);
for(int i : e){
LL t = x[i] - y[i];
if(i > m){
if(!S.empty()){
auto it = --S.end();
while(t - *it <= C && left > 0){
if(g){
v.emplace_back(t - *it);
}
--left;
--it;
}
}
}else{
S.insert(t);
}
}
S.clear();
solve(l , m , C , g);
solve(m + 1 , r , C , g);
};
LL ans = 0;
for(int bit = 33;bit >= 0;bit --){
ans += 1LL << bit;
left = K;
solve(1 , n , ans , 0);
if(left <= 0){
ans -= 1LL << bit;
}
}
left = K;
solve(1 , n , ans , 1);
++ans;
sort(v.begin() , v.end());
while(left--){
v.emplace_back(ans);
}
for(int x : v){
cout << x << '\n';
}
}
