#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(int tl, int tr) {
if (tl == tr) return new Node(0);
int tm = (tl + tr) / 2;
Node* L = build(tl, tm);
Node* R = build(tm+1, tr);
return new Node(0, L, R);
}
Node* update(Node* v, int tl, int tr, int pos, long long add) {
if (tl == tr) {
return new Node(v->sum + add, nullptr, nullptr);
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
Node* newL = update(v->l, tl, tm, pos, add);
return new Node(v->sum + add, newL, v->r);
} else {
Node* newR = update(v->r, tm+1, tr, pos, add);
return new Node(v->sum + add, v->l, newR);
}
}
long long query(Node* v, int tl, int tr, int l, int r) {
if (!v || l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return v->sum;
int tm = (tl + tr) / 2;
return query(v->l, tl, tm, l, r)
+ query(v->r, tm+1, tr, l, r);
}
ll M = 250'010;
vector<ll> cnt(M,1), last(M,0);
ll n;
ll inf = 1e18;
vector<Point> pkt;
vector<ll> X, Y;
vector<Node*> root(M);
int base = 1<<18;
int 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;
}
}
int amount(vector<ll> &x, ll l, ll r) {
return upper_bound(x.begin(), x.end(), r) - lower_bound(x.begin(), x.end(), l);
}
ll kwadrat(ll x, ll y, ll r) {
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 = lower_bound(Y.begin(), Y.end(), y-r) - Y.begin();
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 = 0;
ll hi = 4e9;
if(cnt[i]==n) return inf;
for(int l=32; l>=0; --l) {
if(kwadrat(pkt[i].x, pkt[i].y, (1LL<<l) + last[i]) <= cnt[i]) last[i] += (1LL<<l);
}
if(kwadrat(pkt[i].x, pkt[i].y, last[i]) <= cnt[i]) last[i]++;
cnt[i]++;
return last[i];
}
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) {
pq.push({-find_nxt(i), i});
}
for(ll ile=0; ile<2*k; ++ile){
if(ile%2==0) cout << -pq.top().first << "\n";
ll i =pq.top().second;
pq.pop();
pq.push({-find_nxt(i), i});
}
return 0;
}
