#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 1e6 + 5;
int n;
struct BIT
{
int dt[NM];
void reset()
{
memset(dt, 0, sizeof dt);
}
void upd(int i, int v)
{
for (; i < NM; i += i & -i)
dt[i] += v;
}
int get(int i)
{
if (i < 0)
return 0;
int res = 0;
for (; i; i -= i & -i)
res += dt[i];
return res;
}
int get(int l, int r)
{
return get(r) - get(l - 1);
}
}bit;
int k;
vector<int> nen;
pair<int, int> a[NM];
int find(int x)
{
return lower_bound(nen.begin(), nen.end(), x) - nen.begin() + 1;
}
int check(int x)
{
bit.reset();
int pt = 1, res = 0;
for (int i = 1; i <= n; i++)
{
while (pt < i && a[pt].fi < a[i].fi - x)
bit.upd(find(a[pt++].se), -1);
res += bit.get(find(a[i].se - x), find(a[i].se + x + 1) - 1);
bit.upd(find(a[i].se), 1);
}
return res;
}
map<int, int> mp;
set<pair<int, int>> s;
int dist(int i, int j)
{
return max(abs(a[i].fi - a[j].fi), abs(a[i].se - a[j].se));
}
void trace(int x)
{
int pt = 1;
for (int i = 1; i <= n; i++)
{
while (pt < i && a[pt].fi < a[i].fi - x)
s.erase({a[pt].se, pt++});
auto it = s.lower_bound({a[i].se - x, 0});
while (it != s.end() && (*it).fi <= a[i].se + x)
{
mp[dist((*it).se, i)]++;
it = next(it);
}
s.insert({a[i].se, i});
}
for (auto p : mp)
{
for (int i = 0; i < p.se; i++)
cout << p.fi << endl;
k -= p.se;
}
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i].fi >> a[i].se;
a[i].fi += a[i].se;
a[i].se = a[i].fi - 2 * a[i].se;
nen.push_back(a[i].se);
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
sort(a + 1, a + 1 + n);
int l = -1, r = 5e9;
while (l < r - 1)
{
int m = l + r >> 1;
if (check(m) >= k)
r = m;
else
l = m;
}
trace(r - 1);
for (int i = 1; i <= k; i++)
cout << r << endl;
}
signed main()
{
fastIO
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
int tc = 1; // cin >> tc;
while (tc--)
solve();
}
