#include <stdio.h>
#include <sys/time.h>
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
#define X 2000000002
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], n;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
void solve1(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
int i, i_, x, y, xl, xr, yl, yr, s;
if (n == 0) {
if (ss_[0] > 1)
xx_[0] = X + 1, yy_[0] = X + 1, ss_[0] = 1;
return;
}
xl = X, xr = -X, yl = X, yr = -X;
for (i = 0; i < n; i++) {
i_ = ii[i], x = xx[i_], y = yy[i_];
xl = min(xl, x), xr = max(xr, x);
yl = min(yl, y), yr = max(yr, y);
}
s = max(max(xr - xl, yr - yl), 1);
if (ss_[0] > s)
xx_[0] = xl, yy_[0] = yl, ss_[0] = s;
}
void solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static int ypl[N], ypr[N], yql[N], yqr[N];
int i, xl, xr, xp, xq, y, yl, yr, s;
long long x0, y0, s0, x1, y1, s1;
if (n == 0) {
if (max(ss_[0], ss_[1]) > 1) {
xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
xx_[1] = X + 1, yy_[1] = -(X + 2), ss_[1] = 1;
}
return;
}
xl = xx[ii[0]], xr = xx[ii[n - 1]];
yl = X, yr = -X;
for (i = 0; i < n; i++) {
y = yy[ii[i]];
ypl[i] = yl = min(yl, y);
ypr[i] = yr = max(yr, y);
}
yl = X, yr = -X;
for (i = n - 1; i >= 0; i--) {
y = yy[ii[i]];
yql[i] = yl = min(yl, y);
yqr[i] = yr = max(yr, y);
}
for (i = -1; i < n; i++) {
xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]];
if (xp == xq)
continue;
if (i == -1)
s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
else
s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1), x0 = xp - s0, y0 = ypr[i] - s0;
if (i + 1 == n)
s1 = 1, x1 = X + 1, y1 = -(X + 2);
else
s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1), x1 = xq, y1 = yqr[i + 1] - s1;
s = max(s0, s1);
if (max(ss_[0], ss_[1]) > s) {
xx_[0] = x0, yy_[0] = y0, ss_[0] = s0;
xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
}
}
}
void solve21(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static long long xx1[3], yy1[3], ss1[3];
static int ii1[N], ii2[N];
int n1, n2, h, i, i_, lower, upper;
lower = -X, upper = X;
while (upper - lower > 1) {
int y = ((long long) lower + upper) / 2;
n1 = n2 = 0;
for (i = 0; i < n; i++) {
i_ = ii[i];
if (yy[i_] <= y)
ii1[n1++] = i_;
else
ii2[n2++] = i_;
}
ss1[0] = ss1[1] = ss1[2] = INF;
solve2(ii1, n1, xx1, yy1, ss1), solve1(ii2, n2, xx1 + 2, yy1 + 2, ss1 + 2);
if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(ss1[0], ss1[1]), ss1[2]))
for (h = 0; h < 3; h++)
xx_[h] = xx1[h], yy_[h] = yy1[h], ss_[h] = ss1[h];
if (max(ss1[0], ss1[1]) < ss1[2])
lower = y;
else
upper = y;
}
}
void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static int ypl[N], ypr[N], yql[N], yqr[N], ysl[N], ysr[N], ytl[N], ytr[N];
int i, i_, j, xl, xr, xp, xq, xs, xt, y, yl, yr;
long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
if (n == 0) {
if (max(max(ss_[0], ss_[1]), ss_[2]) > 1) {
xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
xx_[1] = 0, yy_[1] = -(X + 2), ss_[1] = 1;
xx_[2] = X + 1, yy_[2] = -(X + 2), ss_[2] = 1;
}
return;
}
xl = xx[ii[0]], xr = xx[ii[n - 1]];
yl = X, yr = -X;
for (i = 0; i < n; i++) {
y = yy[ii[i]];
ypl[i] = yl = min(yl, y);
ypr[i] = yr = max(yr, y);
}
yl = X, yr = -X;
for (i = n - 1; i >= 0; i--) {
y = yy[ii[i]];
yql[i] = yl = min(yl, y);
yqr[i] = yr = max(yr, y);
}
for (i = 0; i + 1 < n; i++) {
xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]];
s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1);
s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1);
if (s0 > s1)
break;
}
i_ = i;
yl = X, yr = -X;
for (i = i_ - 1; i >= 0; i--) {
y = yy[ii[i]];
ysl[i] = yl = min(yl, y);
ysr[i] = yr = max(yr, y);
}
yl = X, yr = -X;
for (i = i_; i < n; i++) {
y = yy[ii[i]];
ytl[i] = yl = min(yl, y);
ytr[i] = yr = max(yr, y);
}
for (i = i_; i >= 0; i--) {
xp = i == 0 ? -(X + 1) : xx[ii[i - 1]], xs = xx[ii[i]];
for (j = i_; j < n; j++) {
xt = xx[ii[j]], xq = j + 1 == n ? X + 1 : xx[ii[j + 1]];
yl = min(i == i_ ? X : ysl[i], ytl[j]), yr = max(i == i_ ? -X : ysr[i], ytr[j]);
if (xp < xs && xt < xq && max(yr - yl, 1) <= (long long) xq - xp - 2) {
if (i == 0)
s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
else
s0 = max(max(xp - xl, ypr[i - 1] - ypl[i - 1]), 1), x0 = xp - s0, y0 = ypr[i - 1] - s0;
if (j + 1 == n)
s2 = 1, x2 = X + 1, y2 = -(X + 2);
else
s2 = max(max(xr - xq, yqr[j + 1] - yql[j + 1]), 1), x2 = xq, y2 = yqr[j + 1] - s2;
s1 = max(max(xt - xs, yr - yl), 1), x1 = min(xs, xq - 1 - s1), y1 = yr - s1;
if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(s0, s1), s2)) {
xx_[0] = x0, yy_[0] = y0, ss_[0] = s0;
xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
xx_[2] = x2, yy_[2] = y2, ss_[2] = s2;
}
}
}
}
}
int main() {
static int ii[N];
static long long xx_[3], yy_[3], ss_[3];
int k, h, i, r;
long long tmp;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
ii[i] = i;
}
ss_[0] = INF;
if (k == 1)
solve1(ii, n, xx_, yy_, ss_);
else if (k == 2)
for (r = 0; r < 2; r++) {
sort(ii, 0, n);
solve2(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
}
else if (k == 3) {
for (r = 0; r < 4; r++) {
sort(ii, 0, n);
solve21(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = -yy_[h], yy_[h] = tmp, xx_[h] -= ss_[h];
}
for (r = 0; r < 2; r++) {
sort(ii, 0, n);
solve111(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
}
}
for (h = 0; h < k; h++)
printf("%lld %lld %lld\n", xx_[h], yy_[h], ss_[h]);
return 0;
}
