#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000];
pair<ll,ll> p[1100000];
vector<ll> seg1[550000],seg2[550000];
vector<ll> tmp,ans,v,u;
void add()
{
ll i;
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
// printf("!");
merge(ans.begin(),ans.end(),v.begin(),v.end(),tmp.begin());
// printf("?");
for(i=0;i<k;i++)
{
ans[i]=tmp[i];
}
}
void f1(ll x)
{
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(seg1[x*2].begin(),seg1[x*2].end(),seg1[x*2+1].begin(),seg1[x*2+1].end(),tmp.begin());
ll i;
for(i=0;i<k;i++)
{
seg1[x][i]=tmp[i];
}
if(x==1)
return;
f1(x/2);
}
void f2(ll x)
{
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(seg2[x*2].begin(),seg2[x*2].end(),seg2[x*2+1].begin(),seg2[x*2+1].end(),tmp.begin());
ll i;
for(i=0;i<k;i++)
{
seg2[x][i]=tmp[i];
}
if(x==1)
return;
f2(x/2);
}
vector<ll> g1(ll x,ll y,ll z)
{
vector<ll> cur;
cur.resize(k);
fill(cur.begin(),cur.end(),inf);
if(y<l||x>r)
return cur;
if(l<=x&&y<=r)
return seg1[z];
vector<ll> v1,v2;
v1=g1(x,(x+y)/2,z*2);
v2=g1((x+y)/2+1,y,z*2+1);
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
ll u,i;
for(i=0;i<k;i++)
{
cur[i]=tmp[i];
}
return cur;
}
vector<ll> g2(ll x,ll y,ll z)
{
vector<ll> cur;
cur.resize(k);
fill(cur.begin(),cur.end(),inf);
if(y<l||x>r)
return cur;
if(l<=x&&y<=r)
return seg2[z];
vector<ll> v1,v2;
v1=g2(x,(x+y)/2,z*2);
v2=g2((x+y)/2+1,y,z*2+1);
tmp.clear();
tmp.resize(22);
fill(tmp.begin(),tmp.end(),inf);
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
ll u,i;
for(i=0;i<k;i++)
{
cur[i]=tmp[i];
}
return cur;
}
ll tr(ll x)
{
return lower_bound(u.begin(),u.end(),x)-u.begin()+1;
}
int main()
{
scanf("%lld %lld",&n,&k);
ans.resize(k);
fill(ans.begin(),ans.end(),inf);
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&x,&y);
p[i]={x,y};
u.push_back(y);
}
sort(u.begin(),u.end());
u.erase(unique(u.begin(),u.end()),u.end());
sort(p+1,p+n+1);
// printf("!");
for(i=1;i<=524288;i++)
{
seg1[i].resize(k);
seg2[i].resize(k);
fill(seg1[i].begin(),seg1[i].end(),inf);
fill(seg2[i].begin(),seg2[i].end(),inf);
}
for(i=1;i<=n;i++)
{
// printf("%lld\n",i);
x=p[i].first;
y=p[i].second;
z=tr(y);
l=z;
r=262144;
v=g1(1,262144,1);
for(j=0;j<v.size();j++)
{
v[j]+=x-y;
}
// printf("?");
add();
// printf("!");
l=1;
r=z-1;
v=g2(1,262144,1);
for(j=0;j<v.size();j++)
{
v[j]+=x+y;
}
//printf("@");
add();
seg1[z+262143].push_back(y-x);
seg2[z+262143].push_back(-y-x);
sort(seg1[z+262143].begin(),seg1[z+262143].end());
seg1[z+262143].erase(--seg1[z+262143].end());
sort(seg2[z+262143].begin(),seg2[z+262143].end());
seg2[z+262143].erase(--seg2[z+262143].end());
f1((z+262143)/2);
f2((z+262143)/2);
}
//printf("\n\n\n\n%lld\n",ans.size());
for(i=0;i<k;i++)
{
// printf("!");
printf("%lld\n",ans[i]);
}
}
