#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
struct Square{
ll l, x, y;
Square(){}
Square(ll _l, ll _x, ll _y): l(_l), x(_x), y(_y) {}
void print(){printf("%lld %lld %lld\n", x, y, l);}
};
pair<int, int> a[100100], a0[100100];
ll mn[100100], mx[100100];
void solve1(int n){
sort(a+1, a+n+1);
int y1 = a[1].second, y2 = a[1].second;
for (int i=1;i<=n;i++){
y1 = min(y1, a[i].second);
y2 = max(y2, a[i].second);
}
Square ans(max(max(a[n].first-a[1].first, y2-y1), 1LL), a[1].first, y1);
ans.print();
}
pair<int, pair<Square, Square>> solve2x(int n){
sort(a+1, a+n+1);
a[n+1].first = 1e9+100;
mn[n] = a[n].second;
mx[n] = a[n].second;
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);
}
int y1 = 1e9, y2 = -1e9, ans = 2e9 + 100;
pair<Square, Square> ret;
for (int i=1;i<=n;i++){
y1 = min(y1, a[i].second);
y2 = max(y2, a[i].second);
int L1 = max(y2-y1, a[i].first-a[1].first);
int L2 = max(mx[i+1]-mn[i+1], a[n].first-a[i+1].first);
L1 = max(L1, 1LL);
L2 = max(L2, 1LL);
if (ans > max(L1, L2) && a[i].first < a[i+1].first){
ans = max(L1, L2);
ret = make_pair(Square(L1, (ll)a[i].first-L1, (ll)y1), Square(L2, (ll)a[i+1].first, (ll)mn[i+1]));
}
}
return {ans, ret};
}
void solve2(int n){
auto [ans1, p1] = solve2x(n);
for (int i=1;i<=n;i++) swap(a[i].first, a[i].second);
auto [ans2, p2] = solve2x(n);
auto p = p1;
if (ans2 < ans1){
p = p2;
swap(p.first.x, p.first.y);
swap(p.second.x, p.second.y);
}
p.first.print();
p.second.print();
}
vector<Square> rans3;
pair<ll, ll> b[100100];
bool solve3x(int s, int e, ll L, ll mnx){
if (s>e){
rans3.emplace_back(1, 3e9-5000, 3e9-5000);
rans3.emplace_back(1, 3e9-6000, 3e9-6000);
return 1;
}
sort(b+s, b+e+1);
b[e+1].first = 2e9;
mn[e] = b[e].second;
mx[e] = b[e].second;
for (int i=e-1;i>=s;i--){
mn[i] = min(mn[i+1], b[i].second);
mx[i] = max(mx[i+1], b[i].second);
}
ll y1 = 1e18, y2 = -1e18, ans = 1e18;
pair<Square, Square> ret;
for (int i=s;i<=e;i++){
y1 = min(y1, (ll)b[i].second);
y2 = max(y2, (ll)b[i].second);
ll L1 = max(y2-y1, (ll)b[i].first-b[s].first);
ll L2 = max((ll)mx[i+1]-mn[i+1], (ll)b[e].first-b[i+1].first);
L1 = max(L1, 1LL);
L2 = max(L2, 1LL);
if (ans > max(L1, L2) && b[i].first < b[i+1].first){
ll X = min(b[i+1].first-1-L1, (ll)b[s].first);
if (X < mnx) continue;
ans = max(L1, L2);
ret = make_pair(Square(L1, X, y1), Square(L2, b[i+1].first, mn[i+1]));
}
}
if (ans <= L){
rans3.push_back(ret.first);
rans3.push_back(ret.second);
return 1;
}
return 0;
}
bool solve3xx(int n, ll L){
rans3.clear();
sort(a+1, a+n+1);
ll y1 = 1e18, y2 = -1e18;
for (int i=1;i<=n+1;){
int r = i;
ll py1 = y1, py2 = y2;
while(r<=n && a[i].first==a[r].first){
y1 = min(y1, (ll)a[r].second);
y2 = max(y2, (ll)a[r].second);
++r;
}
ll len = max((ll)a[i].first - a[1].first, y2-y1);
if (len > L || i==n+1){
if (py1==1e18) return 0;
for (int j=i;j<=n;j++) b[j] = a[j];
if (solve3x(i, n, L, a[i-1].first+1)){
ll rlen = max((ll)a[i-1].first - a[1].first, py2-py1);
rlen = max(rlen, 1LL);
rans3.emplace_back(rlen, a[i-1].first-rlen, py1);
return 1;
}
return 0;
}
i = r;
}
assert(0);
}
bool solve3xy(int n, ll L){
rans3.clear();
sort(a+1, a+n+1);
ll y1 = 1e18, y2 = -1e18;
for (int i=1;i<=n+1;){
int r = i;
ll py1 = y1, py2 = y2;
while(r<=n && a[i].first==a[r].first){
y1 = min(y1, (ll)a[r].second);
y2 = max(y2, (ll)a[r].second);
++r;
}
ll len = max((ll)a[i].first - a[1].first, y2-y1);
if (len > L || i==n+1){
if (py1==1e18) return 0;
for (int j=i;j<=n;j++) b[j] = {a[j].second, a[j].first};
if (solve3x(i, n, L, -1e18)){
for (auto &S:rans3) swap(S.x, S.y);
ll rlen = max((ll)a[i-1].first - a[1].first, py2-py1);
rlen = max(rlen, 1LL);
rans3.emplace_back(rlen, a[i-1].first-rlen, py1);
return 1;
}
return 0;
}
i = r;
}
assert(0);
}
bool ok(int n, ll L){
for (int i=1;i<=n;i++) a[i] = a0[i];
//if (L==2) printf("\nok\n");
if (solve3xx(n, L)) return 1;
//if (L==2) printf("ok\n");
if (solve3xy(n, L)) return 1;
for (int i=1;i<=n;i++) a[i].first = -a[i].first;
//if (L==2) printf("ok\n");
if (solve3xx(n, L)){
for (auto &S:rans3) S.x = -S.x-S.l;
return 1;
}
if (solve3xy(n, L)){
for (auto &S:rans3) S.x = -S.x-S.l;
return 1;
}
for (int i=1;i<=n;i++) a[i].first = -a[i].first;
///swap xy
for (int i=1;i<=n;i++) swap(a[i].first, a[i].second);
//if (L==2) printf("ok\n");
if (solve3xx(n, L)){
for (auto &S:rans3) swap(S.x, S.y);
return 1;
}
//if (L==2) printf("ok\n");
if (solve3xy(n, L)){
for (auto &S:rans3) swap(S.x, S.y);
return 1;
}
for (int i=1;i<=n;i++) a[i].first = -a[i].first;
//if (L==2) printf("ok\n");
if (solve3xy(n, L)){
for (auto &S:rans3) S.x = -S.x-S.l;
for (auto &S:rans3) swap(S.x, S.y);
return 1;
}
if (solve3xx(n, L)){
for (auto &S:rans3) S.x = -S.x-S.l;
for (auto &S:rans3) swap(S.x, S.y);
return 1;
}
return 0;
}
void solve3(int n){
ll l = 1, r = 2e9+100, ans = -1;
while(l<=r){
ll m = (l+r)/2;
if (ok(n, m)) r = m-1, ans = m;
else l = m+1;
}
assert(ans!=-1);
assert(ok(n, ans));
for (auto &S:rans3) S.print();
}
signed main(){
int n, k;
scanf("%lld %lld", &n, &k);
for (int i=1;i<=n;i++) scanf("%lld %lld", &a[i].first, &a[i].second);
//for (int i=1;i<=n;i++) a[i].first = i, a[i].second = -i;
for (int i=1;i<=n;i++) a0[i] = a[i];
if (k==1) solve1(n);
if (k==2) solve2(n);
if (k==3) solve3(n);
return 0;
}
