#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
ll n, k;
pll p[MAXN];
vector<ll> res;
set<pll> s;
void input() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
p[i].f = x + y;
p[i].s = x - y;
}
sort(p, p + n);
}
ll dist(int i, int j) {
return max(abs(p[i].f - p[j].f), abs(p[i].s - p[j].s));
}
bool check(ll x) {
res.clear();
s.clear();
int cnt = 0;
for (int i = 0; i < n; i++) {
while (cnt < i && p[i].f - p[cnt].f > x) {
s.erase({p[cnt].s, cnt});
cnt++;
}
if (!s.empty()) {
auto h = s.lower_bound({p[i].s - x, -1});
for (; h != s.end(); h++) {
if (p[(*h).s].s > p[i].s + x)
break;
res.push_back(dist((*h).s, i));
if (res.size() >= k)
return true;
}
}
s.insert({p[i].s, i});
}
return false;
}
void findAns() {
ll l = 0, r = 4e9;
while (r - l > 1) {
ll mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
check(l);
sort(res.begin(), res.end());
for (auto x : res)
cout << x << '\n';
for (int i = 0; i < k - (int)res.size(); i++)
cout << r << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
input();
findAns();
return 0;
}
