#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
const int N = 1e6+10;
const long long L = 0, R = 8e9;
const long long C = 4e9;
struct Segtree{
int tree[4*N], lf[4*N], rf[4*N], sz;
int join(int a, int b){
return a+b;
}
void start(){
memset(tree, 0, sizeof tree);
memset(lf, -1, sizeof lf);
memset(rf, -1, sizeof rf);
}
void build(){
tree[1] = 0;
lf[1] = rf[1] = -1;
sz = 1;
}
int calc(int node){
int res = 0;
if(lf[node] != -1) res += tree[lf[node]];
if(rf[node] != -1) res += tree[rf[node]];
return res;
}
void update(int node, long long l, long long r, long long pos, int val){
if(l == r){
tree[node] += val;
return;
}
long long mid = (l+r)/2;
if(l <= pos and pos <= mid){
if(lf[node] == -1){
sz++;
lf[node] = sz;
tree[lf[node]] = 0;
}
update(lf[node], l, mid, pos, val);
}
else{
if(rf[node] == -1){
sz++;
rf[node] = sz;
tree[rf[node]] = 0;
}
update(rf[node], mid+1, r, pos, val);
}
tree[node] = calc(node);
return;
}
int query(int node, long long l, long long r, long long tl, long long tr){
if(node == -1) return 0;
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
long long mid = (tl+tr)/2;
return join(query(lf[node], l, r, tl, mid), query(rf[node], l, r, mid+1, tr));
}
void clear(int node, long long l, long long r){
long long mid = (l+r)/2;
if(lf[node] != -1) clear(lf[node], l, mid);
lf[node] = -1;
if(rf[node] != -1) clear(rf[node], mid+1, r);
rf[node] = -1;
tree[node] = 0;
sz = 1;
return;
}
} seg;
vector <long long> answer;
long long atx, aty;
struct SegtreeSet{
int tree[4*N], lf[4*N], rf[4*N], sz;
map <long long, int> ss[4*N];
int join(int a, int b){
return a+b;
}
void start(){
memset(tree, 0, sizeof tree);
memset(lf, -1, sizeof lf);
memset(rf, -1, sizeof rf);
}
void build(){
tree[1] = 0;
lf[1] = rf[1] = -1;
sz = 1;
}
int calc(int node){
int res = 0;
if(lf[node] != -1) res += tree[lf[node]];
if(rf[node] != -1) res += tree[rf[node]];
return res;
}
void updateadd(int node, long long l, long long r, long long pos, int val){
if(l == r){
tree[node]++;
ss[node][val]++;
return;
}
long long mid = (l+r)/2;
if(l <= pos and pos <= mid){
if(lf[node] == -1){
sz++;
lf[node] = sz;
tree[lf[node]] = 0;
}
updateadd(lf[node], l, mid, pos, val);
}
else{
if(rf[node] == -1){
sz++;
rf[node] = sz;
tree[rf[node]] = 0;
}
updateadd(rf[node], mid+1, r, pos, val);
}
tree[node] = calc(node);
return;
}
void updateremove(int node, long long l, long long r, long long pos, int val){
if(l == r){
tree[node]--;
ss[node][val]--;
return;
}
long long mid = (l+r)/2;
if(l <= pos and pos <= mid){
if(lf[node] == -1){
sz++;
lf[node] = sz;
tree[lf[node]] = 0;
}
updateremove(lf[node], l, mid, pos, val);
}
else{
if(rf[node] == -1){
sz++;
rf[node] = sz;
tree[rf[node]] = 0;
}
updateremove(rf[node], mid+1, r, pos, val);
}
tree[node] = calc(node);
return;
}
void query(int node, long long l, long long r, long long tl, long long tr){
if(node == -1) return;
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
// cout << tl << ' ' << tr << endl;
if(tl == tr){
if(ss[node].empty()) return;
for(auto [valor, qtd] : ss[node]){
for(int i = 0;i < qtd;i++) answer.push_back(max(abs(atx-valor), abs(aty-(tl-C))));
}
return;
}
long long mid = (tl+tr)/2;
if(lf[node] != -1){
if(tree[lf[node]] != 0) query(lf[node], l, r, tl, mid);
}
if(rf[node] != -1){
if(tree[rf[node]] != 0) query(rf[node], l, r, mid+1, tr);
}
return;
}
long long mid = (tl+tr)/2;
query(lf[node], l, r, tl, mid);
query(rf[node], l, r, mid+1, tr);
return;
}
void clear(int node, long long l, long long r){
long long mid = (l+r)/2;
if(lf[node] != -1) clear(lf[node], l, mid);
lf[node] = -1;
if(rf[node] != -1) clear(rf[node], mid+1, r);
rf[node] = -1;
tree[node] = 0;
sz = 1;
return;
}
} seg2;
vector <pair <long long, long long>> v;
long long solve(long long D){
seg.clear(1, L, R);
seg.build();
int r = 0;
long long res = 0;
for(int i = 0;i < v.size();i++){
while(r < v.size()){
if(v[r].first-v[i].first > D) break;
seg.update(1, L, R, v[r].second+C, +1);
r++;
}
res += seg.query(1, v[i].second-D+C, v[i].second+D+C, L, R)-1;
seg.update(1, L, R, v[i].second+C, -1);
}
return res;
}
void solve2(long long D){
seg2.start();
seg2.clear(1, L, R);
seg2.build();
int r = 0;
long long res = 0;
for(int i = 0;i < v.size();i++){
atx = v[i].first;
aty = v[i].second;
while(r < v.size()){
if(v[r].first-v[i].first > D) break;
seg2.updateadd(1, L, R, v[r].second+C, v[r].first);
r++;
}
seg2.updateremove(1, L, R, v[i].second+C, v[i].first);
seg2.query(1, v[i].second-D+C, v[i].second+D+C, L, R);
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, k;
cin >> n >> k;
for(int i = 0;i < n;i++){
int a, b;
cin >> a >> b;
v.push_back({a+b, b-a});
}
sort(v.begin(), v.end());
seg.start();
seg.build();
long long l = 0, r = 4e9;
long long ans = r;
while(l <= r){
long long mid = (l+r)/2;
if(solve(mid) >= k){
r = mid-1;
}
else{
ans = mid;
l = mid+1;
}
}
solve2(ans);
while(answer.size() < k){
answer.push_back(ans+1);
}
sort(answer.begin(), answer.end());
for(auto x : answer){
cout << x << '\n';
}
return 0;
}
