#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
#define X 1000000001
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;
int *zz;
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 (zz[ii[j]] == zz[i_])
j++;
else if (zz[ii[j]] < zz[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 = (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;
}
}
int ypl[N], ypr[N], yql[N], yqr[N], ysl[N], ysr[N], ytl[N], ytr[N], xl, xr, xp, xq, xs, xt, yl, yr;
long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
void try(int *ii, int n, int i, int j, long long *xx_, long long *yy_, long long *ss_) {
xp = i == 0 ? -(X + 1) : xx[ii[i - 1]], xs = xx[ii[i]];
xt = xx[ii[j]], xq = j + 1 == n ? X + 1 : xx[ii[j + 1]];
yl = min(ysl[i], ytl[j]), yr = max(ysr[i], ytr[j]);
if (xp < xs && xt < xq && (i == 0 || j + 1 == n || max(yr - yl, 1) <= 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, j + 1 == n ? X + 1 : xq - 1 - s1), y1 = yl;
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;
}
}
}
void update(int *ft, int i, int n, int x) {
while (i < n) {
ft[i] = max(ft[i], x);
i |= i + 1;
}
}
int query(int *ft, int i) {
int x = -1;
while (i >= 0) {
x = max(x, ft[i]);
i &= i + 1, i--;
}
return x;
}
void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static int ii1[N], jj1[N], ii2[N], jj2[N], ii_[N], iil[N], iir[N], jj_[N], jjl[N], jjr[N];
static int uu[N], vv[N], ft1[N], ft2[N];
int ni, nj, i, i_, j, j_, y, lower, upper;
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 = xx[ii[i]], xq = 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;
ysl[i_] = X, ysr[i_] = -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--)
try(ii, n, i, n - 1, xx_, yy_, ss_);
for (j = i_; j < n; j++) {
try(ii, n, 0, j, xx_, yy_, ss_);
try(ii, n, i_, j, xx_, yy_, ss_);
}
ni = 0;
for (i = i_ - 1; i > 0; i--)
if (xx[ii[i]] > xx[ii[i - 1]])
ii1[ni++] = i;
nj = 0;
for (j = i_; j + 1 < n; j++)
if (xx[ii[j]] < xx[ii[j + 1]])
jj1[nj++] = j;
for (i = 0, j = nj - 1; i < ni; i++) {
i_ = ii1[i];
while (j > 0) {
j_ = jj1[j];
xp = xx[ii[i_ - 1]], xs = xx[ii[i_]];
xt = xx[ii[j_]], xq = xx[ii[j_ + 1]];
yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]);
s1 = max(max(xt - xs, yr - yl), 1), s2 = max(max(xr - xq, yqr[j_ + 1] - yql[j_ + 1]), 1);
if (s1 <= s2)
break;
j--;
}
jj_[i] = j;
}
for (i = 0, j = 0; i < ni; i++) {
i_ = ii1[i];
while (j < nj && ysl[i_] <= ytl[jj1[j]])
j++;
jjl[i] = j;
}
for (i = 0, j = 0; i < ni; i++) {
i_ = ii1[i];
while (j < nj && ysr[i_] >= ytr[jj1[j]])
j++;
jjr[i] = j;
}
for (j = 0, i = ni - 1; j < nj; j++) {
j_ = jj1[j];
while (i > 0) {
i_ = ii1[i];
xp = xx[ii[i_ - 1]], xs = xx[ii[i_]];
xt = xx[ii[j_]], xq = xx[ii[j_ + 1]];
yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]);
s1 = max(max(xt - xs, yr - yl), 1), s0 = max(max(xp - xl, ypr[i_ - 1] - ypl[i_ - 1]), 1);
if (s1 <= s0)
break;
i--;
}
ii_[j] = i;
}
for (i = 0, j = 0; j < nj; j++) {
j_ = jj1[j];
while (i < ni && ytl[j_] <= ysl[ii1[i]])
i++;
iil[j] = i;
}
for (i = 0, j = 0; j < nj; j++) {
j_ = jj1[j];
while (i < ni && ytr[j_] >= ysr[ii1[i]])
i++;
iir[j] = i;
}
/* ysl[i_] <= ytl[j_] && ysr[i_] >= ytr[j_] */
for (i = 0; i < ni; i++) {
i_ = ii1[i];
lower = -1, upper = min(jjl[i], jjr[i]);
while (upper - lower > 1) {
j = (lower + upper) / 2, j_ = jj1[j];
if (ysr[i_] - ysl[i_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2)
upper = j;
else
lower = j;
}
lower = upper, upper = min(jjl[i], jjr[i]) - 1;
if (lower > upper)
continue;
j = jj_[i];
if (j < lower)
try(ii, n, i_, jj1[lower], xx_, yy_, ss_);
else if (j > upper)
try(ii, n, i_, jj1[upper], xx_, yy_, ss_);
else
try(ii, n, i_, jj1[j], xx_, yy_, ss_);
}
/* ytl[j_] <= ysl[i_] && ytr[j_] >= ysr[i_] */
for (j = 0; j < nj; j++) {
j_ = jj1[j];
lower = -1, upper = min(iil[j], iir[j]);
while (upper - lower > 1) {
i = (lower + upper) / 2, i_ = ii1[i];
if (ytr[j_] - ytl[j_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2)
upper = i;
else
lower = i;
}
lower = upper, upper = min(iil[j], iir[j]) - 1;
if (lower > upper)
continue;
i = ii_[j];
if (i < lower)
try(ii, n, ii1[lower], j_, xx_, yy_, ss_);
else if (i > upper)
try(ii, n, ii1[upper], j_, xx_, yy_, ss_);
else
try(ii, n, ii1[i], j_, xx_, yy_, ss_);
}
for (i = 0; i < ni; i++)
ii2[i] = i;
for (j = 0; j < nj; j++)
jj2[j] = j;
/* ysl[i_] <= ytl[j_] && ysr[i_] < ytr[j_] */
for (i = 0; i < ni; i++) {
i_ = ii1[i];
uu[i] = ysl[i_] - (xx[ii[i_ - 1]] + 1);
}
for (j = 0; j < nj; j++) {
j_ = jj1[j];
vv[j] = ytr[j_] - (xx[ii[j_ + 1]] - 1);
}
zz = uu, sort(ii2, 0, ni);
zz = vv, sort(jj2, 0, nj);
memset(ft1, -1, nj * sizeof *ft1);
memset(ft2, -1, nj * sizeof *ft2);
for (i = 0, j = 0; i < ni; i++) {
lower = jjr[i], upper = jjl[i] - 1;
if (lower > upper)
continue;
i_ = ii2[i];
while (j < nj && uu[i_] >= vv[j_ = jj2[j]])
update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++;
j_ = query(ft1, min(jj_[i_], upper));
if (j_ >= lower)
try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower));
if (j_ <= upper)
try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
}
/* ysl[i_] > ytl[j_] && ysr[i_] >= ytr[j_] */
for (i = 0; i < ni; i++) {
i_ = ii1[i];
uu[i] = -(ysr[i_] + (xx[ii[i_ - 1]] + 1));
}
for (j = 0; j < nj; j++) {
j_ = jj1[j];
vv[j] = -(ytl[j_] + (xx[ii[j_ + 1]] - 1));
}
zz = uu, sort(ii2, 0, ni);
zz = vv, sort(jj2, 0, nj);
memset(ft1, -1, nj * sizeof *ft1);
memset(ft2, -1, nj * sizeof *ft2);
for (i = 0, j = 0; i < ni; i++) {
lower = jjl[i], upper = jjr[i] - 1;
if (lower > upper)
continue;
i_ = ii2[i];
while (j < nj && uu[i_] >= vv[j_ = jj2[j]])
update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++;
j_ = query(ft1, min(jj_[i_], upper));
if (j_ >= lower)
try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower));
if (j_ <= upper)
try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
}
}
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++) {
zz = xx, 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++) {
zz = xx, 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++) {
zz = xx, 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;
}
