// Lights, camera, b*tch smile, even when you wanna die
// He said he'd love me all his life
// But that life was too short
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
struct bod { ll x, y; };
bool cmpy(bod a, bod b) { return a.y < b.y; }
struct sgt2d
{
int n;
vector<vector<ll> > st, sx;
vector<ll> cs;
void init(vector<bod> v)
{
for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
sort(cs.begin(), cs.end()), cs.erase(unique(cs.begin(), cs.end()), cs.end());
n = cs.size();
st.assign(n * 2, {}), sx.assign(n * 2, {});
sort(v.begin(), v.end(), cmpy);
for (bod i : v)
{
int x = lower_bound(cs.begin(), cs.end(), i.x) - cs.begin();
for (x += n; x > 0; x >>= 1) st[x].push_back(i.y), sx[x].push_back(i.x);
}
}
int query(ll lx, ll rx, ll ly, ll ry)
{
lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
int ans = 0;
for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1)
{
if (lx & 1) ans += upper_bound(st[lx].begin(), st[lx].end(), ry) - lower_bound(st[lx].begin(), st[lx].end(), ly), lx++;
if (rx & 1) rx--, ans += upper_bound(st[rx].begin(), st[rx].end(), ry) - lower_bound(st[rx].begin(), st[rx].end(), ly);
}
return ans;
}
void query2(ll lx, ll rx, ll ly, ll ry, vector<ll> &ans, bod b, ll lim)
{
lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1)
{
if (lx & 1)
{
int li = lower_bound(st[lx].begin(), st[lx].end(), ly) - st[lx].begin();
int ri = upper_bound(st[lx].begin(), st[lx].end(), ry) - st[lx].begin();
for (int i = li; i < ri; i++) ans.push_back(max(abs(st[lx][i] - b.y), abs(sx[lx][i] - b.x)));
lx++;
}
if (rx & 1)
{
rx--;
int li = lower_bound(st[rx].begin(), st[rx].end(), ly) - st[rx].begin();
int ri = upper_bound(st[rx].begin(), st[rx].end(), ry) - st[rx].begin();
for (int i = li; i < ri; i++) ans.push_back(max(abs(st[rx][i] - b.y), abs(sx[rx][i] - b.x)));
}
}
}
};
sgt2d st;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<bod> o(n), v(n);
for (int i = 0; i < n; i++)
{
//o[i].x = rand() * 10000 + rand(), o[i].y = rand() * 10000 + rand();
cin >> o[i].x >> o[i].y;
v[i].x = o[i].x + o[i].y;
v[i].y = o[i].x - o[i].y;
}
random_shuffle(v.begin(), v.end());
st.init(v);
ll lo = 1, hi = 1e10;
while (lo < hi)
{
ll mi = (lo + hi) / 2;
ll cnt = 0;
for (int i = 0; i < n; i++)
{
cnt += st.query(v[i].x - mi, v[i].x, v[i].y - mi, v[i].y) - 1;
if (cnt >= k) break;
cnt += st.query(v[i].x - mi, v[i].x - 1, v[i].y + 1, v[i].y + mi);
if (cnt >= k) break;
}
if (cnt >= k) hi = mi;
else lo = mi + 1;
}
vector<ll> ans;
for (int i = 0; i < n; i++)
{
st.query2(v[i].x - lo + 1, v[i].x, v[i].y - lo + 1, v[i].y, ans, v[i], lo - 1);
st.query2(v[i].x - lo + 1, v[i].x - 1, v[i].y + 1, v[i].y + lo - 1, ans, v[i], lo - 1);
}
sort(ans.begin(), ans.end(), greater<ll>());
while (ans.size() && ans.back() == 0) ans.pop_back();
reverse(ans.begin(), ans.end());
while (ans.size() > k) ans.pop_back();
while (ans.size() < k) ans.push_back(lo);
for (int i = 0; i < k; i++) cout << ans[i] << "\n";
return 0;
}
