// The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
// Spring Training Camp/Qualifying Trial
// March 20–23, 2021 (Komaba, Tokyo)
// Contest Day 2 – Road Construction
// JOI21_road_construction
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pll pair<ll,ll>
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
#define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
const ll maxn = 1e6+5, inf=1e18;
struct Segment{
ll a, b1, b2, sgn, idx;
Segment(){}
Segment(ll a, ll b1, ll b2, ll sgn, ll idx): a(a), b1(b1), b2(b2), sgn(sgn), idx(idx){}
bool operator<(const Segment &rhs) const{
return a < rhs.a;
}
};
struct FenwickTree{
int n;
vector<int> bit;
FenwickTree(){}
FenwickTree(int n): n(n), bit(n+1, 0){}
void update(int idx, int v){
if(idx <= 0) return;
for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
}
long long getSum(int idx){
if(idx <= 0) return 0;
int res = 0;
for(;idx;idx-=idx&-idx) res += bit[idx];
return res;
}
};
ll n,k, L, R, mid, cnt[maxn];
pair<ll,ll> p[maxn];
vector<Segment> all;
vector<ll> values;
FenwickTree fen;
bool check(ll x){
all.clear();
values.clear();
values.push_back(-inf);
f1(i,n){
cnt[i] = 0;
all.push_back(Segment(p[i].first - x - 1, p[i].second - x, p[i].second + x, -1, i));
all.push_back(Segment(p[i].first + x, p[i].second - x, p[i].second + x, 1, i));
values.push_back(all.back().b1);
values.push_back(all.back().b2);
values.push_back(p[i].second);
}
fen = FenwickTree(3*n);
sort(values.begin(), values.end());
sort(all.begin(), all.end());
// S.clear();
ll ptr = 1;
for(Segment item: all){
while(p[ptr].first <= item.a){
// S.insert({p[ptr].second, ptr});
ll ptr_x = lower_bound(values.begin(), values.end(), p[ptr].second) - values.begin();
fen.update(ptr_x, 1);
ptr++;
}
ll ptr_r = lower_bound(values.begin(), values.end(), item.b2) - values.begin();
ll ptr_l = lower_bound(values.begin(), values.end(), item.b1) - values.begin();
cnt[item.idx] += (fen.getSum(ptr_r) - fen.getSum(ptr_l - 1)) * item.sgn;
}
ll tot = 0;
f1(i,n) tot += cnt[i];
tot -= n;
// cout << x << ' ' << tot;el;
tot /= 2;
return tot >= k;
}
set<pair<ll,ll>> S2;
vector<ll> allDist;
void addPath(ll idx1, ll idx2){
allDist.push_back(max(abs(p[idx1].first - p[idx2].first), abs(p[idx1].second - p[idx2].second)));
}
void getAllLess(ll x){
S2.clear();
ll ptr_l = 1, ptr_r = 1;
f1(i,n){
ll a1 = p[i].first - x, a2 = p[i].first + x;
while(p[ptr_r].first <= a2){
S2.insert({p[ptr_r].second, ptr_r});
ptr_r++;
}
while(p[ptr_l].first < a1){
S2.erase({p[ptr_l].second, ptr_l});
ptr_l++;
}
ll b1 = p[i].second - x, b2 = p[i].second + x;
auto it1 = S2.lower_bound({b1, 0});
auto it2 = S2.lower_bound({b2, inf});
while(it1 != it2){
ll idx = (*it1).second;
if(idx < i) addPath(idx, i);
it1++;
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if(fopen(__file_name ".inp", "r")){
freopen(__file_name ".inp","r",stdin);
freopen(__file_name ".out","w",stdout);
}
// code here
cin >> n >> k;
f1(i,n) {
ll x, y;
cin >> x >> y;
p[i] = {x-y,x+y};
}
p[n+1] = {inf, inf};
sort(p+1,p+n+1);
L = 0; R = 4e9;
while(L <= R){
mid = (L + R) / 2;
if(check(mid)) R = mid-1;
else L = mid+1;
}
getAllLess(L-1);
sort(allDist.begin(), allDist.end());
for(ll item: allDist) cout << item << '\n';
for(ll i=allDist.size() + 1;i<=k;i++) cout << L << '\n';
return 0;
}
