#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Point {
ll x, y;
friend bool operator<(Point a, Point b) {
return a.y < b.y;
}
};
struct Node {
ll sum;
Node *l, *r;
Node(ll s=0, Node* l=nullptr, Node* r=nullptr)
: sum(s), l(l), r(r) {}
};
Node* build(ll a, ll b) {
if(a==b) return new Node(0);
Node* m = new Node(0);
ll mid = (a+b)/2;
m->l = build(a,mid);
m->r = build(mid+1,b);
return m;
}
Node* update(Node *root, ll a, ll b, ll p, ll val) {
if(b < p || a > p) return root;
if(a==b) {
return new Node(root->sum + val);
}
ll m = (a+b)/2;
Node* newL = update(root->l, a, m, p, val);
Node* newR = update(root->r, m+1, b, p, val);
return new Node(newL->sum + newR->sum, newL, newR);
}
ll query(Node *root, ll a, ll b, ll l, ll r) {
if(!r || b < l || r < a) return 0;
if(l <= a && b <= r) return root->sum;
ll m = (a+b)/2;
return query(root->l, a, m, l, r) + query(root->r, m+1, b, l, r);
}
ll M = 250'010;
vector<ll> cnt(M,1);
ll n;
ll inf = 1e18;
vector<Point> pkt;
vector<ll> X, Y;
vector<Node*> root(M);
ll base = 1<<18;
ll numer = 1;
void init() {
for(ll i=0; i<n; ++i) X.push_back(pkt[i].x);
sort(X.begin(), X.end());
for(ll i=0; i<n; ++i) Y.push_back(pkt[i].y);
for(ll i=0; i<n; ++i) {
ll idx = lower_bound(X.begin(), X.end(), pkt[i].x) - X.begin();
root[numer] = update(root[numer-1], 0, base-1, idx, 1);
++numer;
}
}
ll kwadrat(ll i, ll r) {
auto[x,y] = pkt[i];
ll a = lower_bound(X.begin(), X.end(), x-r) - X.begin();
ll b = upper_bound(X.begin(), X.end(), x+r) - X.begin() - 1;
ll left = i;
ll right = upper_bound(Y.begin(), Y.end(), y+r) - Y.begin() - 1;
return query(root[right+1], 0, base-1, a,b) - query(root[left],0,base-1,a,b);
}
ll find_nxt(ll i) {
ll lo = i;
ll hi = n-1;
if(cnt[i]==n-i) return inf;
while(lo < hi) {
ll mid = (lo+hi)/2;
if(kwadrat(i, pkt[mid].y - pkt[i].y) > cnt[i]) hi = mid;
else lo = mid+1;
}
ll glowny_r = pkt[lo].y - pkt[i].y;
ll glowny_k = kwadrat(i, glowny_r);
lo = lower_bound(X.begin(), X.end(), pkt[i].x) - X.begin();
hi = n-1;
while(lo < hi) {
ll mid = (lo+hi)/2;
if(kwadrat(i, X[mid] - pkt[i].x) > cnt[i]) hi = mid;
else lo = mid+1;
}
ll x1_r = X[lo] - pkt[i].x;
ll x1_k = kwadrat(i, x1_r);
lo = 0;
hi = lower_bound(X.begin(), X.end(), pkt[i].x) - X.begin();
while(lo < hi) {
ll mid = (lo+hi+1)/2;
if(kwadrat(i, pkt[i].x - X[mid]) > cnt[i]) lo = mid;
else hi = mid-1;
}
ll x2_r = pkt[i].x - X[lo];
ll x2_k = kwadrat(i, x2_r);
if(glowny_k <= cnt[i]) glowny_r = inf;
if(x1_k <= cnt[i]) x1_r = inf;
if(x2_k <= cnt[i]) x2_r = inf;
cnt[i]++;
return min(min(x1_r,x2_r),glowny_r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll k;
cin >> n >> k;
pkt.resize(n);
for(ll i=0; i<n; ++i) {
ll x,y;
cin >> x >> y;
pkt[i] = {x+y,x-y};
}
sort(pkt.begin(), pkt.end());
root[0] = build(0,base-1);
init();
priority_queue<pair<ll, ll>> pq;
for(ll i=0; i<n; ++i) {
ll x = find_nxt(i);
pq.push({-x, i});
}
for(ll ile=0; ile<k; ++ile){
cout << -pq.top().first << "\n";
ll i =pq.top().second;
// cout << "(" << i << ")\n";
pq.pop();
pq.push({-find_nxt(i), i});
}
return 0;
}
