#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#define int long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ppp pair<pii, pii>
#define fst first
#define snd second
using namespace std;
const int INF = 1e9 + 7;
int N, K;
vector<pii> A;
pii B[100001];
ppi sqr;
pii prefMin[100001], sufMin[100001];
pii prefMax[100001], sufMax[100001];
vector<ppi> ans;
inline bool Intersect(const ppi &A, const ppi &B)
{
pii iL = {max(A.fst.fst, B.fst.fst), max(A.fst.snd, B.fst.snd)};
pii iR = {min(A.fst.fst + A.snd, B.fst.fst + B.snd), min(A.fst.snd + A.snd, B.fst.snd + B.snd)};
return (iL.fst <= iR.fst && iL.snd <= iR.snd);
}
inline bool comp(const pii &L, const pii &R) {return make_pair(L.snd, L.fst) < make_pair(R.snd, R.fst);}
inline bool comp2(const ppi &L, const ppi &R) {return make_pair(L.snd, L.fst) > make_pair(R.snd, R.fst);}
vector<pii> use[3];
vector<ppi> tmp;
void brute(int d)
{
if (d < N)
{
for (int i = 0; i < K; i++)
{
use[i].push_back(B[d]);
brute(d + 1);
use[i].pop_back();
}
}
else if (d < N + K)
{
int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
for (const auto &x : use[d - N])
{
mnY = min(mnY, x.snd); mxY = max(mxY, x.snd);
mnX = min(mnX, x.fst); mxX = max(mxX, x.fst);
}
if (use[d - N].size() > 1)
{
if (mxY - mnY > mxX - mnX)
{
tmp.push_back({{mnX, mnY}, mxY - mnY});
brute(d + 1);
tmp.pop_back();
tmp.push_back({{mxX - mxY + mnY, mnY}, mxY - mnY});
brute(d + 1);
tmp.pop_back();
}
else
{
tmp.push_back({{mnX, mnY}, mxX - mnX});
brute(d + 1);
tmp.pop_back();
tmp.push_back({{mnX, mxY - mxX + mnX}, mxX - mnX});
brute(d + 1);
tmp.pop_back();
}
}
else if (use[d - N].size() == 1)
{
tmp.push_back({{mnX, mnY}, 1});
brute(d + 1);
tmp.pop_back();
tmp.push_back({{mnX - 1, mnY}, 1});
brute(d + 1);
tmp.pop_back();
tmp.push_back({{mnX, mnY - 1}, 1});
brute(d + 1);
tmp.pop_back();
tmp.push_back({{mnX - 1, mnY - 1}, 1});
brute(d + 1);
tmp.pop_back();
}
else
{
tmp.push_back({{-2000000000 - 2 * d, -2000000000 - 2 * d}, 1});
brute(d + 1);
tmp.pop_back();
}
}
else
{
bool valid = 1;
for (int i = 0; i < tmp.size(); i++)
{
for (int j = i + 1; j < tmp.size(); j++) valid &= !Intersect(tmp[i], tmp[j]);
}
if (valid)
{
vector<ppi> tmp2 = tmp;
sort(tmp2.begin(), tmp2.end(), comp2);
if (ans.size() && ans[0].snd <= tmp2[0].snd) return;
ans = tmp2;
}
}
}
inline void solve()
{
if (A.size() < 2) return;
for (int i = 0; i < A.size(); i++)
{
prefMin[i] = A[i]; prefMax[i] = A[i];
if (i)
{
prefMin[i].fst = min(prefMin[i - 1].fst, prefMin[i].fst);
prefMin[i].snd = min(prefMin[i - 1].snd, prefMin[i].snd);
prefMax[i].fst = max(prefMax[i - 1].fst, prefMax[i].fst);
prefMax[i].snd = max(prefMax[i - 1].snd, prefMax[i].snd);
}
}
for (int i = A.size() - 1; i >= 0; i--)
{
sufMin[i] = A[i]; sufMax[i] = A[i];
if (i + 1 < N)
{
sufMin[i].fst = min(sufMin[i + 1].fst, sufMin[i].fst);
sufMin[i].snd = min(sufMin[i + 1].snd, sufMin[i].snd);
sufMax[i].fst = max(sufMax[i + 1].fst, sufMax[i].fst);
sufMax[i].snd = max(sufMax[i + 1].snd, sufMax[i].snd);
}
}
for (int i = 0; i + 1 < A.size(); i++)
{
pii aL = prefMin[i], aR = prefMax[i], bL = sufMin[i + 1], bR = sufMax[i + 1];
int sA = max(aR.fst - aL.fst, aR.snd - aL.snd);
int sB = max(bR.fst - bL.fst, bR.snd - bL.snd);
if (sA == 0) {sA = 1;}
if (sB == 0) {sB = 1;}
aL.fst = aR.fst - sA; aL.snd = aR.snd - sA;
if (Intersect({aL, sA}, {bL, sB})) continue;
if (K == 3 && Intersect(sqr, {bL, sB})) continue;
if (K == 3 && Intersect(sqr, {aL, sA})) continue;
vector<ppi> temp;
temp.push_back({aL, sA}); temp.push_back({bL, sB});
if (K == 3) temp.push_back(sqr);
sort(temp.begin(), temp.end(), comp2);
if (ans.size() && ans[0].snd <= temp[0].snd) continue;
ans = temp;
}
}
int32_t main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
for (int i = 0; i < N; i++)
{
cin >> B[i].fst >> B[i].snd;
mnY = min(mnY, B[i].snd); mxY = max(mxY, B[i].snd);
mnX = min(mnX, B[i].fst); mxX = max(mxX, B[i].fst);
}
ans.push_back({{mnX, mnY}, max(1LL, max(mxX - mnX, mxY - mnY))});
for (int j = 1; j < K; j++) ans.push_back({{-2000000000 - 2 * j, -2000000000 - 2 * j}, 1});
if (K == 2)
{
for (int i = 0; i < N; i++) A.push_back(B[i]);
sort(A.begin(), A.end()); solve();
sort(A.begin(), A.end(), comp); solve();
}
else if (K == 3) {brute(0);}
for (int i = 0; i < K; i++)
{
cout << ans[i].fst.fst << " " << ans[i].fst.snd << " " << ans[i].snd << "\n";
}
return 0;
}
