#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long llong;
const int MAXN = 3e5 + 10;
const llong MAXD = 4e9 + 10;
int n, k;
pair < llong, llong > points[MAXN];
void read()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
llong x, y;
cin >> x >> y;
points[i] = {x + y, x - y};
}
sort(points + 1, points + 1 + n);
}
vector < llong > check(llong d)
{
set < pair < llong, llong > > s;
queue < pair < llong, llong > > q;
vector < llong > result;
for(int i = 1; i <= n; i++)
{
while(!q.empty() && q.front().first < points[i].first - d)
{
s.erase({q.front().second, q.front().first});
q.pop();
}
auto beg = s.lower_bound({points[i].second - d, -MAXD});
for(auto it = beg; it != s.end(); it++)
{
if(it->first > points[i].second + d)
break;
result.push_back(max(llabs(points[i].first - it->second), llabs(points[i].second - it->first)));
}
if(result.size() >= k)
return result;
s.insert({points[i].second, points[i].first});
q.push({points[i].first, points[i].second});
}
return result;
}
void solve()
{
llong left = 0;
llong right = MAXD;
llong mid;
while(right - left > 1)
{
mid = left + (right - left) / 2;
if(check(mid).size() >= k)
right = mid;
else
left = mid;
}
vector < llong > v = check(right - 1);
sort(v.begin(), v.end());
for(llong d : v)
{
cout << d << '\n';
}
for(int i = 1; i <= k - v.size(); i++)
{
cout << right << '\n';
}
}
int main()
{
read();
solve();
return 0;
}
