#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
const int N = 250005;
struct points{
long long x, y;
int id;
bool operator < (points oth) const{
if(y == oth.y)
return x < oth.x;
return y < oth.y;
}
};
using ordered_set = tree<points, null_type,less<points>, rb_tree_tag,tree_order_statistics_node_update>;
int n;
points v[N];
points vinit[N];
vector<long long> dist;
long long getdst(int i, int j){
return llabs(vinit[i].x - vinit[j].x) + llabs(vinit[i].y - vinit[j].y);
}
bool cmp(pair<points, bool> a, pair<points, bool> b){
if(a.first.x == b.first.x){
return a.second < b.second;
}
return a.first.x < b.first.x;
}
long long check(long long dst, bool ok){
vector<pair<points, bool>> vc;
for(int i = 1; i <=n; i++){
vc.push_back({v[i], true});
vc.push_back({{v[i].x + dst + 1, v[i].y, v[i].id}, false});
}
sort(vc.begin(), vc.end(), cmp);
ordered_set oset;
long long ans = 0;
for(auto ev:vc){
if(ev.second == false){
ev.first.x -= (dst + 1);
oset.erase(ev.first);
}
else{
points cur = ev.first;
if(ok == true){
auto itrfirst = oset.lower_bound({LLONG_MIN, cur.y - dst});
auto itrlast = oset.upper_bound({LLONG_MAX, cur.y + dst}); /// e pe urm buna
while(itrfirst != itrlast){
points aux = (*itrfirst);
dist.push_back(getdst(aux.id, cur.id));
itrfirst++;
}
}
else{
long long curr = 0;
curr -= oset.order_of_key({LLONG_MIN, cur.y - dst});
curr += oset.order_of_key({LLONG_MIN, cur.y + dst + 1});
ans += curr;
}
oset.insert(cur);
}
}
return ans;
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int k;
cin>>n>>k;
for(int i = 1; i<=n; i++){
int x, y;
cin>>x>>y;
vinit[i].x = x;
vinit[i].y = y;
v[i].x = x + y;
v[i].y = x - y;
v[i].id = i;
}
long long dst = 0;
for(long long p2 = (1LL <<(32)); p2; p2>>=1){
long long cnt = check(dst + p2, false);
if(cnt < k){
dst += p2;
}
}
check(dst, true);
while(dist.size() < k){
dist.push_back(dst + 1);
}
sort(dist.begin(), dist.end());
for(auto x:dist){
cout<<x<<"\n";
}
return 0;
}
