/*
ID: varunra2
LANG: C++
TASK: road
*/
// we precalculate sqrt(n) smallest values of each point
// it is your value if it is to your left
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define int long long
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
struct bit {
int n;
VI bit;
void init(int _n) {
n = _n;
bit.assign(n + 1, 0);
}
void upd(int ind, int val) {
// debug("in");
// debug(ind);
ind++;
while (ind <= n) {
bit[ind] += val;
ind += (ind & (-ind));
}
// debug("out");
}
int qry(int ind) {
int ret = 0;
// debug("indd");
ind++;
while (ind >= 1) {
ret += bit[ind];
ind -= (ind & (-ind));
}
// debug("outt");
return ret;
}
int qry(int l, int r) { return qry(r) - qry(l - 1); }
} fen;
int n, k;
VII vals;
MPII cmp;
VI pnts;
void init() { vals.resize(n); }
void transform() {
// convert all the points into chebyshev distance
for (int i = 0; i < n; i++) {
int x, y;
tie(x, y) = vals[i];
vals[i].x = x + y;
vals[i].y = x - y;
}
}
void comp() {
for (int i = 0; i < n; i++) {
pnts.PB(vals[i].y);
}
sort(all(pnts));
pnts.erase(unique(all(pnts)), pnts.end());
rep(i, 0, sz(pnts)) cmp[pnts[i]] = i;
}
bool count(int dist) {
fen.init(sz(pnts) + 2);
// VVI evnts;
// for (int i = 0; i < n; i++) {
// evnts.PB({vals[i].x, 0, i});
// evnts.PB({vals[i].x + dist, 1, i});
// }
// sort(all(evnts));
int p2 = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
// remove points
while (vals[i].x - vals[p2].x > dist) {
int pt = lower_bound(all(pnts), vals[p2].y) - pnts.begin();
fen.upd(pt, -1);
p2++;
}
// add contribution
int l = lower_bound(all(pnts), vals[i].y - dist) - pnts.begin();
auto p1 = upper_bound(all(pnts), vals[i].y + dist);
if (p1 != pnts.begin()) {
p1--;
int r = p1 - pnts.begin();
if (l <= r) {
cnt += fen.qry(l, r);
if (cnt >= k) return false;
}
}
// add new point
int pt = lower_bound(all(pnts), vals[i].y) - pnts.begin();
fen.upd(pt, 1);
}
return true;
}
int dst(int i, int j) {
return max(abs(vals[i].x - vals[j].x), abs(vals[i].y - vals[j].y));
}
VI gen(int dist) {
VI ret;
set<PII> st;
// VVI evnts;
// for (int i = 0; i < n; i++) {
// evnts.PB({vals[i].x, 0, i});
// evnts.PB({vals[i].x + dist, 1, i});
// }
// sort(all(evnts));
int p2 = 0;
for (int i = 0; i < n; i++) {
while (vals[i].x - vals[p2].x > dist) {
st.erase(MP(vals[p2].y, p2));
p2++;
}
auto it = st.lower_bound(MP(vals[i].y - dist, -1));
while (it != st.end()) {
if ((*it).x > vals[i].y + dist) break;
ret.PB(dst(i, (*it).y));
it++;
}
st.insert(MP(vals[i].y, i));
}
return ret;
}
int32_t main() {
// #ifndef ONLINE_JUDGE
// freopen("meetings2.in", "r", stdin);
// freopen("meetings2.out", "w", stdout);
// #endif
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
init();
trav(x, vals) cin >> x.x >> x.y;
transform();
sort(all(vals));
comp();
// int x = -1;
// for (int b = (int)4e9; b >= 1; b /= 2) {
// while (count(x + b)) x += b;
// }
// auto ret = gen(x);
int s = 0, e = 4e9;
while (s != e) {
int m = (s + e + 1) / 2;
if (count(m))
s = m;
else
e = m - 1;
}
if (k == 1) {
cout << s + 1 << '\n';
exit(0);
}
VI ret = gen(s);
while (sz(ret) < k) ret.PB(s + 1);
sort(all(ret));
trav(x, ret) cout << x << '\n';
debug(s + 1);
return 0;
}
