#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, K, X[250005], Y[250005], A[250005], B[250005], ft[250005], SB[250005];
ii T[250005];
vector<int> out, vec;
int ls(int x) { return x & -x; }
int conv(int p) {
auto it = upper_bound(SB + 1, SB + 1 + N, p);
return it - SB - 1;
}
int conv2(int p) {
auto it = lower_bound(SB + 1, SB + 1 + N, p);
return it - SB;
}
int qry(int p) {
p = conv(p);
int r = 0;
for (; p; p -= ls(p)) r += ft[p];
return r;
}
void upd(int p, int v) {
p = conv(p);
for (; p <= N; p += ls(p)) ft[p] += v;
}
struct node {
node *left, *right;
int S, E, ptr;
vector<int> val;
node(int _s, int _e) : S(_s), E(_e) {
if (S == E) return;
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
}
void del(int p) {
ptr++;
if (S == E) return;
int M = (S + E) >> 1;
if (p <= M) left->del(p);
else right->del(p);
}
void upd(int p, int v) {
val.pb(v);
if (S == E) return;
int M = (S + E) >> 1;
if (p <= M) left->upd(p, v);
else right->upd(p, v);
}
void find_all(int l, int r) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
for (int i = ptr; i < (int)val.size(); i++) {
vec.pb(val[i]);
}
return;
}
left->find_all(l, r);
right->find_all(l, r);
}
} *root;
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> X[i] >> Y[i];
A[i] = (X[i] + Y[i]);
B[i] = (X[i] - Y[i]);
SB[i] = B[i];
T[i] = mp(A[i], B[i]);
}
sort(T + 1, T + 1 + N);
sort(SB + 1, SB + 1 + N);
for (int i = 1; i <= N; i++) {
tie(A[i], B[i]) = T[i];
}
int lo = 0, hi = (int)1e10, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2, cnt = 0;
for (int i = 1; i <= N; i++) {
ft[i] = 0;
}
for (int i = 1, ptr = 1; i <= N; i++) {
while (A[i] - A[ptr] > mid) {
assert(ptr < i);
upd(B[ptr], -1);
ptr++;
}
cnt += qry(B[i] + mid) - qry(B[i] - mid - 1);
upd(B[i], 1);
}
if (cnt >= K) ans = mid, hi = mid - 1;
else lo = mid + 1;
}
root = new node(1, N);
for (int i = 1, ptr = 1; i <= N; i++) {
while (A[i] - A[ptr] > ans - 1) {
assert(ptr < i);
root->del(conv(B[ptr]));
ptr++;
}
vec.clear();
root->find_all(conv2(B[i] - (ans - 1)), conv(B[i] + (ans - 1)));
for (auto j : vec) {
out.eb(max(llabs(A[i] - A[j]), llabs(B[i] - B[j])));
}
root->upd(conv(B[i]), i);
}
sort(out.begin(), out.end());
for (auto i : out) cout << i << '\n';
for (int i = 0; i < K - (int)out.size(); i++) cout << ans << '\n';
}
