#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X...) cerr<<"["#X"]: ", [](auto...$) {((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define int long long
const int INF = 1e18+7;
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define eb emplace_back
vector<pair<int, int> > pts;
int check(int d, bool f = false)
{
vector<vector<int> > graph(pts.size());
for(auto& v : pts)
for(auto& u : pts)
if(u != v && max(abs(u.fi-v.fi), abs(u.se-v.se)) <= d)
graph[&u-&(*pts.begin())].eb(&v-&(*pts.begin()));
vector<int> depth(pts.size(), -1);
int res = 0;
int cnt = 0;
vector<int> artpt(pts.size());
function<int(int, int)> dfs = [&](int a, int de)
{
depth[a] = de;
int lw = de;
int chld = 0;
int cnr = 0;
for(auto v : graph[a])
if(depth[v] == -1)
{
chld++;
int l = dfs(v, de+1);
if(artpt[v] != 0) chld--, cnr++;
if(l >= de && de != 0 && artpt[v] == 0)
artpt[a] = graph[a].size(), cnt++;
lw = min(lw, l);
}
else if(depth[a] - depth[v] > 1)
lw = min(lw, depth[v]);
if(de == 0 && chld >= 2)
artpt[a] = graph[a].size()-cnr, cnt++;
return lw;
};
for(int i=0;i<pts.size();i++)
if(depth[i] == -1)
{
dfs(i, 0);
res += cnt+1;
cnt = 0;
}
if(f)
{
vector<bool> vis(pts.size());
int x = INF, y = INF;
function<void(int)> tr = [&](int a)
{
x = min(pts[a].fi, x);
y = min(pts[a].se, y);
vis[a] = true;
for(auto v : graph[a])
if(vis[v] == false && artpt[v] == 0)
tr(v);
else if(--artpt[v] == 0)
vis[v] = true,
x = min(pts[v].fi, x),
y = min(pts[v].se, y);
};
for(int i=0;i<pts.size();i++)
{
if(vis[i] == false && artpt[i] == false)
{
x = y = INF;
tr(i);
cout<<x<<" "<<y<<" "<<d<<endl;
}
}
}
return res;
}
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin>>n>>k;
pts.resize(n);
for(auto& [x, y] : pts)
cin>>x>>y;
int p = 0, q = 1e9+7;
while(p != q-1)
{
int pol = (p+q)/2;
debug(p, q, pol, check(pol));
if(check(pol) <= k)
q = pol;
else
p = pol;
}
check(q, true);
}
