#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
#define x first
#define y second
typedef pair<ll, ll> pt;
const int N = 250005;
int n, k;
pt a[N];
vi byX;
ll Ys[N]; int Ysz;
int lessY(ll y) {
return int(lower_bound(Ys, Ys+Ysz, y) - Ys);
}
int ft[N];
void update(int pos, int val) {
for(; pos < N; pos += pos & -pos) ft[pos] += val;
}
int query(int l, int r, int ret = 0) {
for(l--; l > 0; l -= l & -l) ret -= ft[l];
for(; r > 0; r -= r & -r) ret += ft[r];
return ret;
}
ll count(ll d) {
memset(ft, 0, sizeof ft);
ll pairs = 0;
int ptr = 1;
for(int i = 1; i <= n; ++i) {
while(a[ptr].x < a[i].x - d) {
int j = lessY(a[ptr++].y) + 1;
update(j, -1);
}
{
int l = lessY(a[i].y - d) + 1;
int r = lessY(a[i].y + d + 1);
int me = lessY(a[i].y) + 1;
pairs += query(l, r);
update(me, +1);
}
}
return pairs;
}
vector<ii> Less(ll d) {
using pli = pair<ll, int>;
set<pli> st;
vector<ii> ret;
int ptr = 1;
for(int i = 1; i <= n; ++i) {
while(a[ptr].x <= a[i].x - d) {
st.erase(pli(a[ptr].y, ptr));
ptr++;
}
auto lit = st.upper_bound(pli(a[i].y-d, INT_MAX));
auto rit = st.lower_bound(pli(a[i].y+d, INT_MIN));
for(auto it = lit; it != rit; ++it) {
ret.emplace_back(i, it -> se);
}
st.insert(pli(a[i].y, i));
}
return ret;
}
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
scanf("%d %d", &n, &k);
// assert(n <= 1000);
// assert(k == 1);
for(int i = 1; i <= n; ++i) {
int x, y;
scanf("%d %d", &x, &y);
a[i].x = x + y;
a[i].y = x - y;
Ys[i-1] = a[i].y;
}
sort(a+1, a+1+n);
sort(Ys, Ys+n);
Ysz = int(unique(Ys, Ys+n) - Ys);
ll lo = 1, hi = 4000000000LL, low = -1;
while(lo <= hi) {
ll mid = (lo + hi) >> 1;
if(count(mid) >= k) {
low = mid;
hi = mid-1;
} else {
lo = mid+1;
}
}
auto les = Less(low);
vector<ll> ans;
for(auto [i, j] : les) {
ans.emplace_back(max(abs(a[i].x - a[j].x), abs(a[i].y - a[j].y)));
}
for(int i = 0; i < k-sz(les); ++i) ans.emplace_back(low);
sort(all(ans));
for(ll x : ans) printf("%lld\n", x);
return 0;
}
