#include <bits/stdc++.h> // pA
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int N = 3e5+5;
const ll INF = 1e18;
ll n, Q;
pll p[N];
multiset<pll> st;
vector<ll> v;
//#define test
inline bool chk(ll w)
{
ll i, L=1, x, y;
st.clear(), v.clear();
for (i=1; i <= n; ++i)
{
while (p[i].F-p[L].F > w)
{
#ifdef test
debug(i), debug(L), debug(w), endl;
#endif
st.erase(st.find({p[L].S, p[L].F}));
++L;
}
for (auto it = st.lower_bound({p[i].S, -INF}); it != st.end(); ++it)
{
x = it->S, y = it->F;
if (y-p[i].S > w) break;
v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
if (SZ(v) >= Q) return 1;
}
auto it = st.lower_bound({p[i].S, -INF});
if (it != st.begin())
{
--it;
for ( ; ; --it)
{
x = it->S, y = it->F;
if (p[i].S-y > w) break;
v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
if (SZ(v) >= Q) return 1;
if (it == st.begin()) break;
}
}
st.insert({p[i].S, p[i].F});
#ifdef test
debug(i), endl;
for (auto x : st) cerr << x.F << ' ' << x.S << '\n';
#endif
}
return 0;
}
int main(void)
{ IO
ll i, lb, mid, ub, x, y;
cin >> n >> Q;
for (i=1; i <= n; ++i) cin >> x >> y, p[i] = {x+y, x-y};
sort(p+1, p+n+1);
#ifndef test
lb = 0, ub = 1e18;
while (lb < ub)
{
mid = (lb+ub)>>1;
if (chk(mid)) ub = mid;
else lb = mid + 1;
}
chk(lb-1);
sort(all(v));
for (i=0; i < min(Q, SZ(v)); ++i) cout << v[i] << '\n';
for (i=0; i < max(Q-SZ(v), 0LL); ++i) cout << lb << '\n';
#else
endl;
for (i=1; i <= n; ++i) debug(p[i].F), debug(p[i].S), endl;
endl;
chk(2);
endl;
for (ll x : v) debug(x), endl;
#endif
return 0;
}
