#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll inf=0x7f7f7f7f7f7f7f7f;
struct node
{
	int pos[2];
}a[250010];
int cur,cnt=0;
ll ans[250010];
priority_queue<ll>q;
bool cmp(node x,node y)
{
	return x.pos[cur]<y.pos[cur];
}
ll get_dis(int x,int y)
{
	return llabs(a[x].pos[0]-a[y].pos[0])+llabs(a[x].pos[1]-a[y].pos[1]);
}
struct KDT
{
	int root;
	struct kd_tree
	{
		int ls,rs,pos[2],mx[2],mn[2];
	}tree[250010];
	#define lson(rt) (tree[rt].ls)
	#define rson(rt) (tree[rt].rs)
	int build_rt(int id)
	{
		int rt=id;
		lson(rt)=rson(rt)=0;
		for(int i=0;i<=1;i++)
			tree[rt].pos[i]=tree[rt].mx[i]=tree[rt].mn[i]=a[id].pos[i];
		return rt;
	}
	void pushup(int rt)
	{
		for(int i=0;i<=1;i++)
		{
			tree[rt].mx[i]=tree[rt].mn[i]=tree[rt].pos[i];
			if(lson(rt)!=0)
			{
				tree[rt].mx[i]=max(tree[rt].mx[i],tree[lson(rt)].mx[i]);
				tree[rt].mn[i]=min(tree[rt].mn[i],tree[lson(rt)].mn[i]);
			}
			if(rson(rt)!=0)
			{
				tree[rt].mx[i]=max(tree[rt].mx[i],tree[rson(rt)].mx[i]);
				tree[rt].mn[i]=min(tree[rt].mn[i],tree[rson(rt)].mn[i]);
			}
		}
	}
	void build(int &rt,int l,int r,int dir)
	{
		int mid=(l+r)/2;  cur=dir;
		nth_element(a+l,a+mid,a+r+1,cmp);  rt=build_rt(mid);
		if(l<=mid-1)  build(lson(rt),l,mid-1,dir^1);
		if(mid+1<=r)  build(rson(rt),mid+1,r,dir^1);
		pushup(rt);
	}
	ll cost(int rt,int pos)
	{
		ll ans=0;
		for(int i=0;i<=1;i++)
		{
			if(a[pos].pos[i]<tree[rt].mn[i])  ans+=tree[rt].mn[i]-a[pos].pos[i];
			if(a[pos].pos[i]>tree[rt].mx[i])  ans+=a[pos].pos[i]-tree[rt].mx[i];
		}
		return ans;
	}
	void query(int rt,int l,int r,int pos)
	{
		int mid=(l+r)/2;
		if(rt!=pos&&get_dis(rt,pos)<q.top())
		{
			q.pop();  q.push(get_dis(rt,pos));
		}
		ll fl=((l<=mid-1)?cost(lson(rt),pos):inf);
		ll fr=((mid+1<=r)?cost(rson(rt),pos):inf); 
		if(fl<q.top()&&fr<q.top())
		{
			if(fl<fr)
			{
				query(lson(rt),l,mid-1,pos);
				if(fr<q.top())  query(rson(rt),mid+1,r,pos);
			}
			else
			{
				query(rson(rt),mid+1,r,pos);
				if(fl<q.top())  query(lson(rt),l,mid-1,pos);
			}
		}
		else  if(fl<q.top())  query(lson(rt),l,mid-1,pos);
		else  if(fr<q.top())  query(rson(rt),mid+1,r,pos);
	}
}K;
int main()
{
// #define Isaac
#ifdef Isaac
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n,k,i;
	cin>>n>>k;  k*=2;
	for(i=1;i<=n;i++)  cin>>a[i].pos[0]>>a[i].pos[1];
	for(i=1;i<=k;i++)  q.push(inf);
	K.build(K.root,1,n,0);
	for(i=1;i<=n;i++)  K.query(K.root,1,n,i);
	for(i=k;i>=1;i--)
	{
		ans[i]=q.top();  q.pop();
	}
	for(i=1;i<=k;i+=2)  cout<<ans[i]<<endl;
	return 0;
}