#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
struct SegTree{
ll cnt = 0;
struct Node{
vector <ll> V;
ll chl = -1;
ll chr = -1;
};
vector <Node> st;
void get(ll &id) {
if (id == -1) {
st.push_back({{}, -1, -1});
id = ++cnt;
}
}
void add(ll &id, ll l, ll r, ll x, ll y) {
get(id);
if (l == r) {
st[id].V.push_back(y);
return;
}
ll mid = (l+r)/2;
if (x <= mid) {
ll tmp = st[id].chl;
add(tmp, l, mid, x, y);
st[id].chl = tmp;
}
else {
ll tmp = st[id].chr;
add(tmp, mid+1, r, x, y);
st[id].chr = tmp;
}
}
void build(ll id, ll l, ll r) {
if (st[id].chl == -1 && st[id].chr == -1) {
sort(st[id].V.begin(), st[id].V.end());
return;
}
ll mid = (l+r)/2;
if (st[id].chr == -1) {
build(st[id].chl, l, mid);
st[id].V = st[st[id].chl].V;
}
else if (st[id].chl == -1) {
build(st[id].chr, mid+1, r);
st[id].V = st[st[id].chr].V;
}
else {
build(st[id].chl, l, mid);
build(st[id].chr, mid+1, r);
int i = 0, j = 0;
while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
if (st[st[id].chl].V[i] <= st[st[id].chr].V[j]) st[id].V.push_back(st[st[id].chl].V[i++]);
else st[id].V.push_back(st[st[id].chr].V[j++]);
}
while (i < st[st[id].chl].V.size()) st[id].V.push_back(st[st[id].chl].V[i++]);
while (j < st[st[id].chr].V.size()) st[id].V.push_back(st[st[id].chr].V[j++]);
}
}
ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
if (id == -1 || xr < l || r < xl) return 0;
else if (xl <= l && r <= xr) {
auto itL = lower_bound(st[id].V.begin(), st[id].V.end(), yl);
auto itR = lower_bound(st[id].V.begin(), st[id].V.end(), yr+1);
return itR-itL;
}
ll mid = (l+r)/2;
return query(st[id].chl, l, mid, xl, xr, yl, yr) + query(st[id].chr, mid+1, r, xl, xr, yl, yr);
}
}ST;
ll n, f, k, x, l = 0, rt, r = 4e9, mid;
array <ll, 2> A[250000];
void solve(ll u) {
f = 0;
for (int i=0; i<n; ++i) {
f += ST.query(rt, 0LL, (ll)4e9, max(0LL, A[i][0]+A[i][1]-u), min((ll)4e9, A[i][0]+A[i][1]+u), A[i][0]-A[i][1]-u, A[i][0]-A[i][1]+u);
}
f -= n;
f /= 2;
}
int main() {
ST.st.push_back({{}, -1, -1});
cin >> n >> k;
for (int i=0; i<n; ++i) {
cin >> A[i][0] >> A[i][1];
A[i][0] += (ll)1e9, A[i][1] += (ll)1e9;
ST.add(rt, 0LL, (ll)4e9, A[i][0]+A[i][1], A[i][0]-A[i][1]);
}
ST.build(rt, 0LL, (ll)4e9);
while (true) {
while (l < r) {
mid = (l+r)/2;
solve(mid);
if (f > x) r = mid;
else l = mid+1;
}
solve(l);
while (x < min(f, k)) {
cout << l << '\n';
++x;
}
if (x == k) break;
++l;
r = 4e9;
}
}
