#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, k, lb, rb, mid, res;
array<int, 3> p[250000];
vector<int> g;
struct SEGMENT_TREE
{
long long tree[1000000], num;
vector<long long> con;
inline void Init()
{
fill_n(tree, 1e6, 1e18);
}
inline void Set(int ind, int l, int r, int x, long long v)
{
if (r < x || x < l)
{
return;
}
if (l == r)
{
tree[ind] = v;
return;
}
int m = (l + r) >> 1;
Set(ind << 1, l, m, x, v);
Set(ind << 1 | 1, m + 1, r, x, v);
tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
}
inline void Get(int ind, int l, int r, int x, int y, long long v, long long dist, int mode)
{
if (r < x || y < l || tree[ind] + v > dist)
{
return;
}
if (l == r)
{
num++;
if (mode)
{
con.push_back(tree[ind] + v);
}
return;
}
int m = (l + r) >> 1;
Get(ind << 1, l, m, x, y, v, dist, mode);
if (num < k)
{
Get(ind << 1 | 1, m + 1, r, x, y, v, dist, mode);
}
}
inline void Check(int x, int y, long long v, long long dist, int mode)
{
num = 0;
if (mode)
{
con.clear();
}
if (x <= y)
{
Get(1, 1, n, x, y, v, dist, mode);
}
}
} st1, st2;
inline bool Comp(const array<int, 3> &ina, const array<int, 3> &inb)
{
return ina[1] < inb[1];
}
inline int Cal(int x)
{
int cur = 0;
st1.Init();
st2.Init();
for (int i = 0; i < n && cur <= k; ++i)
{
st1.Check(1, p[i][2], p[i][0] + p[i][1], x, 0);
st1.Set(1, 1, n, p[i][2], -p[i][0] - p[i][1]);
st2.Check(p[i][2] + 1, n, p[i][0] - p[i][1], x, 0);
st2.Set(1, 1, n, p[i][2], -p[i][0] + p[i][1]);
cur += st1.num + st2.num;
}
return cur;
}
int main()
{
setup();
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> p[i][0] >> p[i][1];
}
sort(p, p + n, Comp);
for (int i = 0; i < n; ++i)
{
p[i][2] = i + 1;
}
sort(p, p + n);
lb = 0;
rb = 2e9;
while (lb <= rb)
{
mid = (lb + rb) >> 1;
if (Cal(mid) < k)
{
lb = mid + 1;
}
else
{
rb = mid - 1;
res = mid;
}
}
st1.Init();
st2.Init();
for (int i = 0; i < n; ++i)
{
st1.Check(1, p[i][2], p[i][0] + p[i][1], res - 1, 1);
st1.Set(1, 1, n, p[i][2], -p[i][0] - p[i][1]);
st2.Check(p[i][2] + 1, n, p[i][0] - p[i][1], res - 1, 1);
st2.Set(1, 1, n, p[i][2], -p[i][0] + p[i][1]);
for (auto &j : st1.con)
{
g.push_back(j);
}
for (auto &j : st2.con)
{
g.push_back(j);
}
}
while (g.size() < k)
{
g.push_back(res);
}
sort(g.begin(), g.end());
for (auto &i : g)
{
cout << i << "\n";
}
return 0;
}
