#include<bits/stdc++.h>
using namespace std;
long long n,k;
pair<long long,long long> p[250001];
void read()
{
cin>>n>>k;
for(long long i=1;i<=n;i++)
{
cin>>p[i].first>>p[i].second;
long long x=p[i].first;
long long y=p[i].second;
p[i].first=x-y;
p[i].second=x+y;
}
sort(p+1,p+n+1);
}
vector<long long> v;
bool check(long long x)
{
set<pair<long long,long long> > s;
long long l=1;
//cout<<"! "<<x<<endl;
v.clear();
for(long long i=2;i<=n;i++)
{
pair<long long,long long> sw={p[i-1].second,p[i-1].first};
s.insert(sw);
while(l<i&&p[i].first-p[l].first>x)
{
sw={p[l].second,p[l].first};
s.erase(sw);
l++;
}
auto it=s.lower_bound({p[i].second-x,(long long)-1e9});
while(it!=s.end()&&abs((*it).first-p[i].second)<=x)
{
pair<long long,long long> c=*it;
//cout<<"+ "<<c.first<<" "<<c.second<<" "<<p[i].first<<" "<<(*it).first<<endl;
v.push_back(max(abs(c.first-p[i].second),abs(c.second-p[i].first)));
if(v.size()==k)return 1;
it++;
}
//cout<<i<<" > "<<l<<" "<<r<<endl;
}
return 0;
}
void solve()
{
/*for(int i=1;i<=n;i++)
cout<<p[i].first<<" > "<<p[i].second<<endl;*/
long long d=0;
long long l=0,r=2*1e9;
while(l<=r)
{
long long m=(l+r)/2;
//cout<<m<<endl;
if(check(m))
{
d=m;
r=m-1;
}
else l=m+1;
}
check(d-1);
sort(v.begin(),v.end());
for(long long i=0;i<v.size();i++)
cout<<v[i]<<endl;
for(long long i=v.size();i<k;i++)
cout<<d<<endl;
}
int main()
{
read();
solve();
return 0;
}
