#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Answer {
ll ans = 2e9 + 7;
vector<vector<ll>> res;
void norm(int k) {
int t = 0;
ll x = 2.5e9, y = 2.5e9;
while (res.size() < k) {
res.push_back({x, y, 1});
t += 1;
if (t & 1) {
x = -x;
}
if (t & 2) {
y = -y;
}
}
}
};
void update(pair<ll, ll> &x, ll y) {
x.first = min(x.first, y);
x.second = max(x.second, y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<ll, ll>> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
Answer ans{};
ans.ans = 2e9 + 7;
if (k >= 1) {
ll minx = 2e9, maxx = -2e9, miny = 2e9, maxy = -2e9;
for (auto &[x, y] : a) {
minx = min(minx, x);
maxx = max(maxx, x);
miny = min(miny, y);
maxy = max(maxy, y);
}
ll d = max({1LL, maxy - miny, maxx - minx});
ans.ans = d;
ans.res = {vector<ll>{minx, miny, d}};
}
if (k >= 2) {
for (int t = 0; t < 2; ++t) {
Answer now{};
sort(a.begin(), a.end());
vector<ll> mn(n + 1, 2e9), mx(n + 1, -2e9);
for (int i = n - 1; i >= 0; --i) {
mn[i] = min(mn[i + 1], a[i].second);
mx[i] = max(mx[i + 1], a[i].second);
}
ll mny = 2e9, mxy = -2e9;
for (int i = 0; i < n; ++i) {
mny = min(mny, a[i].second);
mxy = max(mxy, a[i].second);
if (i + 1 < n && a[i + 1].first != a[i].first) {
ll d = max({1LL, mxy - mny, mx[i + 1] - mn[i + 1], a[i].first - a[0].first, a.back().first - a[i + 1].first});
if (now.ans > d) {
now.ans = d;
now.res.clear();
int rx = a[i].first;
int ry = mxy;
now.res.push_back({rx - d, ry - d, d});
int lx = a[i + 1].first;
int ly = mn[i + 1];
now.res.push_back({lx, ly, d});
}
}
}
if (t == 1) {
for (auto &f : now.res) {
swap(f[0], f[1]);
}
}
if (ans.ans > now.ans) {
ans = now;
}
for (auto &[x, y]: a) {
swap(x, y);
}
}
}
if (k >= 3) {
for (int swp = 0; swp < 2; ++swp) {
for (int neg = 0; neg < 2; ++neg) {
sort(a.begin(), a.end());
Answer now{};
ll mny = 2e9, mxy = -2e9;
for (int pref = 0; pref < n - 2; ++pref) {
mny = min(mny, a[pref].second);
mxy = max(mxy, a[pref].second);
ll dnow = max({1LL, mxy - mny, a[pref].first - a[0].first});
if (a[pref + 1].first != a[pref].first) {
// case 1: sandwich
pair<ll, ll> Y{2e9, -2e9};
vector<pair<ll, ll>> suf(n + 1, pair<ll, ll>(2e9, -2e9));
for (int i = n - 1; i >= 0; --i) {
suf[i] = suf[i + 1];
update(suf[i], a[i].second);
}
for (int m = pref + 1; m + 1 < n; ++m) {
update(Y, a[m].second);
if (a[m + 1].first != a[m].first && Y.second - Y.first <= a[m + 1].first - a[pref + 1].first - 1) {
ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].first - a[m + 1].first});
ll dm = max({1LL, Y.second - Y.first, a[m].first - a[pref + 1].first});
ll D = max({dm, dr, dnow});
if (now.ans > D) {
now.ans = D;
now.res.clear();
now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
now.res.push_back({a[pref + 1].first, Y.first, dm});
now.res.push_back({a[m + 1].first, suf[m + 1].first, dr});
}
}
}
// case 2: not sandwich
sort(a.begin() + pref + 1, a.end(), [&](auto u, auto v) {
return u.second < v.second;
});
pair<ll, ll> X = {2e9, -2e9};
fill(suf.begin(), suf.end(), pair<ll, ll>(2e9, -2e9));
for (int i = n - 1; i >= 0; --i) {
suf[i] = suf[i + 1];
update(suf[i], a[i].first);
}
for (int m = pref + 1; m + 1 < n; ++m) {
update(X, a[m].first);
ll dm = max({1LL, X.second - X.first, a[m].second - a[pref + 1].second});
ll dr = max({1LL, suf[m + 1].second - suf[m + 1].first, a[n - 1].second - a[m + 1].second});
if (a[m].second != a[m + 1].second) {
ll D = max({dnow, dm, dr});
if (now.ans > D) {
now.ans = D;
now.res.clear();
now.res.push_back({a[pref].first - dnow, mxy - dnow, dnow});
now.res.push_back({X.first, a[m].second - dm, dm});
now.res.push_back({suf[m + 1].first, a[m + 1].second, dr});
}
}
}
sort(a.begin() + pref + 1, a.end());
}
if (now.ans < ans.ans) {
ans = now;
for (auto &f : ans.res) {
if (neg) {
f[0] = -f[0];
}
if (swp) {
swap(f[0], f[1]);
}
}
}
}
for (auto &[x, y] : a) {
x = -x;
}
}
for (auto &[x, y] : a) {
swap(x, y);
}
}
}
ans.norm(k);
for (auto &t : ans.res) {
for (auto x : t) {
cout << x << " ";
}
cout << '\n';
}
return 0;
}
