#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long ma=1e9,inf=1e18;
long long n,d,nn,nm[2],sk[2][100069];
pair<long long,long long> a[4][100069],as[4][100069],a2[100069];
pair<long long,array<long long,2>> rg[100069];
pair<pair<long long,long long>,long long> ca[3],sq[3];
bitset<100069> vtd;
array<long long,2> a0={-inf,-inf};
struct segtree
{
long long l,r,lz;
pair<long long,long long> mxe;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void rst()
{
lz=0;
if(l==r)
{
mxe={-rg[l-1].fr-1,l};
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->rst();
}
mxe=max(p[0]->mxe,p[1]->mxe);
}
}
void blc()
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mxe.fr+=lz;
p[ii]->lz+=lz;
}
lz=0;
}
void ud(long long lh,long long rh,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
mxe.fr+=w;
lz+=w;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh,w);
}
mxe=max(p[0]->mxe,p[1]->mxe);
}
}
pair<long long,long long> qr(long long lh,long long rh)
{
if(l>rh||r<lh)
{
return {-inf,-1};
}
else if(l>=lh&&r<=rh)
{
return mxe;
}
else
{
blc();
return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
}
}
}
sg;
int main()
{
long long i,j,ii,im,u,x,y,x2,y2,k,l,w,p,mn,mx,mn2,lb,rb,lh,rh,md,c=0;
pair<long long,long long> tmp;
bool bad;
scanf("%lld%lld",&n,&d);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
a[0][i]={x,y};
}
for(im=0;im<4;im++)
{
sort(a[im]+1,a[im]+n+1);
for(i=1;i<=n;i++)
{
as[im][i]={a[im][i].sc,i};
}
sort(as[im]+1,as[im]+n+1);
if(im<3)
{
for(i=1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
a[im+1][i]={y,-x};
}
}
}
sg.bd(1,n);
for(lh=1,rh=ma*2;lh<=rh;)
{
md=(lh+rh)/2;
bad=0;
for(im=0;im<4;im++)
{
if(d==1)
{
if(!im)
{
mn=inf;
mx=-inf;
mn2=inf;
for(i=1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a[im][1].fr>md)
{
break;
}
mn2=mn;
}
if(i>n)
{
bad=1;
sq[0]={{a[im][1].fr,mn2},md};
}
}
}
else if(d==2)
{
if(im<2)
{
l=0;
for(ii=0;ii<2;ii++)
{
mn=inf;
mx=-inf;
k=l;
mn2=inf;
for(i=l+1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a[im][l+1].fr>md)
{
break;
}
if(i==n||x!=a[im][i+1].fr)
{
k=i;
mn2=mn;
}
}
if(!ii)
{
ca[ii]={{a[im][k].fr-md,mn2},md};
}
else
{
ca[ii]={{a[im][l+1].fr,mn2},md};
}
l=k;
}
if(i>n)
{
bad=1;
for(j=0;j<d;j++)
{
sq[j]=ca[j];
}
}
}
}
else
{
mn=inf;
mx=-inf;
k=0;
mn2=inf;
vtd.reset();
for(i=1;i<=n;i++)
{
p=as[im][i].sc;
x=a[im][p].fr;
y=a[im][p].sc;
mn=min(mn,x);
mx=max(mx,x);
if(mx-mn>md||y-as[im][1].fr>md)
{
break;
}
if(i==n||y!=as[im][i+1].fr)
{
mn2=mn;
for(;k<i;)
{
k++;
vtd[as[im][k].sc]=1;
}
}
}
ca[0]={{mn2,as[im][k].fr-md},md};
nn=0;
for(i=1;i<=n;i++)
{
if(!vtd[i])
{
nn++;
a2[nn]=a[im][i];
}
}
l=0;
for(ii=0;ii<2;ii++)
{
mn=inf;
mx=-inf;
k=l;
mn2=inf;
for(i=l+1;i<=nn;i++)
{
x=a2[i].fr;
y=a2[i].sc;
mn=min(mn,y);
mx=max(mx,y);
if(mx-mn>md||x-a2[l+1].fr>md)
{
break;
}
if(i==nn||x!=a2[i+1].fr)
{
k=i;
mn2=mn;
}
}
if(!ii)
{
ca[ii+1]={{a2[k].fr-md,mn2},md};
}
else
{
ca[ii+1]={{a2[l+1].fr,mn2},md};
}
l=k;
}
if(i>nn)
{
bad=1;
for(j=0;j<d;j++)
{
sq[j]=ca[j];
}
}
if(im<2)
{
nn=0;
rg[0].fr=-ma*4;
for(i=1;i<=n;i++)
{
x=a[im][i].fr;
y=a[im][i].sc;
if(!nn||x!=rg[nn].fr)
{
nn++;
rg[nn]={x,{y,y}};
}
else
{
rg[nn].sc[0]=min(rg[nn].sc[0],y);
rg[nn].sc[1]=max(rg[nn].sc[1],y);
}
}
rg[nn+1].fr=ma*4;
mn=inf;
mx=-inf;
for(i=1;i<=nn;i++)
{
x=rg[i].fr;
y=rg[i].sc[0];
y2=rg[i].sc[1];
mn=min(mn,y);
mx=max(mx,y2);
if(mx-mn>md||x-rg[1].fr>md)
{
break;
}
}
lb=i-1;
mn=inf;
mx=-inf;
for(i=nn;i;i--)
{
x=rg[i].fr;
y=rg[i].sc[0];
y2=rg[i].sc[1];
mn=min(mn,y);
mx=max(mx,y2);
if(mx-mn>md||rg[nn].fr-x>md)
{
break;
}
}
rb=i+1;
sg.rst();
for(ii=0;ii<2;ii++)
{
nm[ii]=0;
}
for(i=1;i<=nn;i++)
{
x=rg[i].fr;
y=rg[i].sc[0];
y2=rg[i].sc[1];
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
for(;nm[ii]&&rg[sk[ii][nm[ii]]].sc[ii]*u>=y*u;nm[ii]--)
{
sg.ud(sk[ii][nm[ii]-1]+1,sk[ii][nm[ii]],-abs(y-rg[sk[ii][nm[ii]]].sc[ii]));
}
nm[ii]++;
sk[ii][nm[ii]]=i;
swap(y,y2);
}
sg.ud(i,i,y-y2);
if(i+1>=rb)
{
x2=min(rg[i+1].fr-1,x+md);
k=lower_bound(rg+1,rg+nn+1,mp(x2-md,a0))-rg;
l=upper_bound(rg+1,rg+nn+1,mp(x2-1,a0))-rg-1;
tmp=sg.qr(k+1,min(l,lb+1));
if(x2+tmp.fr>=0)
{
lb=tmp.sc-1;
rb=i+1;
break;
}
if(lb+1<=k&&rg[lb+1].fr>=x-md&&md+sg.qr(lb+1,lb+1).fr+rg[lb].fr+1>=0)
{
rb=i+1;
break;
}
}
}
if(i<=nn)
{
bad=1;
mn=inf;
for(i=1;i<=lb;i++)
{
x=rg[i].fr;
y=rg[i].sc[0];
mn=min(mn,y);
}
sq[0]={{x-md,mn},md};
mn=inf;
for(i=nn;i>=rb;i--)
{
x=rg[i].fr;
y=rg[i].sc[0];
mn=min(mn,y);
}
sq[1]={{x,mn},md};
mn=inf;
for(i=lb+1;i<rb;i++)
{
y=rg[i].sc[0];
mn=min(mn,y);
}
x=rg[lb].fr+1;
x2=rg[rb].fr-1;
if(x2-x>md)
{
w=min(x2-x-md,x2-rg[rb-1].fr);
x2-=w;
w=min(x2-x-md,rg[lb+1].fr-x);
x+=w;
}
sq[2]={{x,mn},x2-x};
}
}
}
for(i=0;i<d;i++)
{
x=sq[i].fr.fr;
y=sq[i].fr.sc;
w=sq[i].sc;
sq[i].fr={y,-x-w};
}
}
if(bad)
{
rh=md-1;
}
else
{
lh=md+1;
}
}
for(i=0;i<d;i++)
{
x=sq[i].fr.fr;
y=sq[i].fr.sc;
w=sq[i].sc;
if(x<-ma*3||y<-ma*3||x>ma*3||y>ma*3)
{
x=ma*3;
y=ma*3-c*2;
w=1;
c++;
}
printf("%lld %lld %lld\n",x,y,w);
}
}
