#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 2.5e5+5, mod = 1e9+7, inf = 1e10;
int n, k;
ii a[N];
vector<int> v;
void cal(int x) {
v.clear();
set<ii> st;
int idx = 1;
for (int i=1; i<=n; i++) {
while (idx<=n && a[i].fi-a[idx].fi>x) {
st.erase({a[idx].se, idx});
idx++;
}
auto it = st.lower_bound({a[i].se-x, -inf});
while (it!=st.end() && (*it).fi-a[i].se<=x) {
if (sz(v)>=k) break;
int id = (*it).se;
v.pb(max(abs(a[i].fi-a[id].fi), abs(a[i].se-a[id].se)));
it = next(it);
}
st.insert({a[i].se, i});
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i=1; i<=n; i++) {
int x, y; cin >> x >> y;
a[i] = {x+y, x-y};
}
sort(a+1, a+n+1);
int lo = 0, hi = inf, ans = 0;
while (lo<=hi) {
int mid = (lo+hi)>>1;
cal(mid);
if (sz(v)<k) {
ans = mid;
lo = mid+1;
} else {
hi = mid-1;
}
}
cal(ans);
sort(all(v));
while (sz(v)!=k) v.pb(ans+1);
for (int it: v) cout << it << '\n';
}
