/* author : Dinmukhammed ^_^ */
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
#define ll long long
#define ld long double
const int N=6e5+3;
const ll inf=1e18;
const ll MOD=1e9+7;
ll t[N*60],L[N*60],R[N*60];
int iddd=0;
int n;
int copy(int v){
int nv=++iddd;
t[nv]=t[v];
L[nv]=L[v];
R[nv]=R[v];
return nv;
}
int build(int tl=1,int tr=n+n){
int v=++iddd;
t[v]=inf;
if(tl==tr)return v;
int md=(tl+tr)>>1;
L[v]=build(tl,md);
R[v]=build(md+1,tr);
return v;
}
int upd(int pos,ll x,int v,int tl=1,int tr=n+n){
v=copy(v);
if(tl==tr){
t[v]=x;
return v;
}
int md=(tl+tr)>>1;
if(pos<=md)L[v]=upd(pos,x,L[v],tl,md);
else R[v]=upd(pos,x,R[v],md+1,tr);
t[v]=min(t[L[v]],t[R[v]]);
return v;
}
ll get(int l,int r,int v,int tl=1,int tr=n+n){
if(tl>=l&&tr<=r)return t[v];
if(tl>r||l>tr)return inf;
int md=(tl+tr)>>1;
return min(get(l,r,L[v],tl,md),get(l,r,R[v],md+1,tr));
}
int del(ll x,int v,bool tp,int tl=1,int tr=n+n){
v=copy(v);
if(tl==tr){
t[v]=inf;
return v;
}
int md=(tl+tr)>>1;
if(tp){
if(t[R[v]]<=x)R[v]=del(x,R[v],tp,md+1,tr);
else L[v]=del(x,L[v],tp,tl,md);
}
else{
if(t[L[v]]<=x)L[v]=del(x,L[v],tp,tl,md);
else R[v]=del(x,R[v],tp,md+1,tr);
}
t[v]=min(t[L[v]],t[R[v]]);
return v;
}
int x[N],y[N],hh[N];
bool cmp(int i,int j){
return x[i]<x[j];
}
void Main(){
int k;cin>>n>>k;
vector<int>st1,pos;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i],st1.push_back(y[i]),pos.push_back(i);
sort(st1.begin(),st1.end());
map<int,int>mp;
int id=0;
for(int i=0;i<n;i++){
if(i==0||st1[i]!=st1[i-1])mp[st1[i]]=id;
id++;
}
sort(pos.begin(),pos.end(),cmp);
set<pair<ll,int>>st;
id=0;
vector<int>root1={build()};
vector<int>root2={build()};
for(auto i:pos){
// cout<<x[i]<<" "<<y[i]<<" ";
mp[y[i]]++;
int h=mp[y[i]];
// cout<<h<<"\n";
hh[id]=h;
ll val=min(get(1,h,root1.back())+(ll)x[i]+(ll)y[i],get(h,n+n,root2.back())+(ll)x[i]-(ll)y[i]);
st.insert({val,id});
root1.push_back(upd(h,-(ll)x[i]-(ll)y[i],root1.back()));
root2.push_back(upd(h,-(ll)x[i]+(ll)y[i],root2.back()));
id++;
}
// cout<<"\n";
// for(auto to:st)cout<<to.F<<" "<<to.S<<"\n";
// cout<<"\n";
while(k--){
cout<<st.begin()->F<<"\n";
int v=st.begin()->S;
ll val=st.begin()->F;
st.erase(st.begin());
int i=pos[v];
ll val1=get(1,hh[v],root1[v]);
ll val2=get(hh[v],n+n,root2[v]);
if(val==val2+(ll)x[i]-(ll)y[i]){
// cout<<"2";
root2[v]=del(val2,root2[v],1);
val2=get(hh[v],n+n,root2[v]);
}
else{
// cout<<"1";
root1[v]=del(val1,root1[v],0);
val1=get(1,hh[v],root1[v]);
}
// cout<<val1<<" "<<val2<<"\n";
if(min(val,val1)==inf)continue;
ll res=min(val1+(ll)x[i]+(ll)y[i],val2+(ll)x[i]-(ll)y[i]);
// cout<<res<<" "<<v<<"\n";
st.insert({res,v});
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int tt=1;
// cin>>tt;
while(tt--)Main();
}
