#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define ll long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)
const ll maxn = 3e5 + 10, maxm = 3e3 + 10, oo = 4e9 + 10, lg = 31, sq = 1400, mod = 998244353;
int n, k;
vector<ll> cmp;
vector<int> v[maxn];
pii a[maxn];
ppp b[maxn];
int fen[maxn];
int id(ll x){
return lower_bound(all(cmp), x) - cmp.begin();
}
void add(int i, int val){
for (; i <= n; i += i & -i)
fen[i] += val;
}
int get(int i){
int res = 0;
for (; i > 0; i -= i & -i)
res += fen[i];
return res;
}
int check(ll x){
int j = 1;
ll res = 0;
for (int i = 1; i <= n; i++)
fen[i] = 0;
for (int i = 1; i <= n; i++)
{
while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > x)
{
add(id(a[j].S - a[j].F), -1);
j++;
}
res += get(id(a[i].S - a[i].F + x + 1) - 1) - get(id(a[i].S - a[i].F - x) - 1);
add(id(a[i].S - a[i].F), 1);
}
return res;
}
int p[2][maxn];
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n;i++)
cin >> a[i].F >> a[i].S;
for (int i = 1; i <= n;i++)
b[i] = {a[i].F + a[i].S, a[i]};
sort(b + 1, b + n + 1);
for (int i = 1; i <= n;i++)
a[i] = b[i].S;
for (int i = 1; i <= n;i++)
cmp.push_back(a[i].S - a[i].F);
cmp.push_back(-oo);
sort(all(cmp));
cmp.resize(unique(all(cmp)) - cmp.begin());
for (int i = 1; i <= n;i++)
v[id(a[i].S - a[i].F)].push_back(i);
ll l = 1, r = mod;
while(r - l > 1)
if(check(mid) >= k)
r = mid;
else
l = mid;
vector<ll> ans;
for (int i = 1; i <= k - check(l);i++)
ans.push_back(r);
int j = 1;
for (int i = 1; i <= n; i++)
{
while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l)
{
p[0][id(a[j].S - a[j].F)]++;
j++;
}
for (int o = id(a[i].S - a[i].F - l); o <= id(a[i].S - a[i].F + l + 1) - 1; o++)
for (int ii = p[0][o]; ii < p[1][o];ii++)
ans.push_back(1ll * abs(a[i].F - a[v[o][ii]].F) + abs(a[i].S - a[v[o][ii]].S));
p[1][id(a[i].S - a[i].F)]++;
}
sort(all(ans));
for(auto i : ans)
cout << i << "\n";
}
signed main()
{
threesum;
int t = 1;
//cin >> t;
while(t--)
solve();
}
