#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
node *lc, *rc;
int l, r;
pair<int, int> val;
node(int l, int r) : lc(0), rc(0), l(l), r(r), val({1e18, 0}) {}
} *empt, *lft[250005], *rght[250005], *root[750005];
set<pair<int, pair<int, int> > > s;
int lvers[250005], rvers[250005];
pair<int, int> points[250005];
vector<pair<int, int> > vec;
void build(node *i)
{
if (i->l==i->r)
return;
int mid=(i->l+i->r)/2;
i->lc=new node(i->l, mid);
i->rc=new node(mid+1, i->r);
build(i->lc);
build(i->rc);
}
void upd1(node *pre, node *i, int x, int y)
{
if (i->l==i->r)
{
i->val={y, x};
return;
}
int mid=(i->l+i->r)/2;
if (x<=mid)
{
i->lc=new node(i->l, mid);
upd1(pre->lc, i->lc, x, y);
i->rc=pre->rc;
}
else
{
i->lc=pre->lc;
i->rc=new node(mid+1, i->r);
upd1(pre->rc, i->rc, x, y);
}
i->val=min(i->lc->val, i->rc->val);
}
void upd2(node *em, node *pre, node *i, int x)
{
if (i->l==i->r)
return;
int mid=(i->l+i->r)/2;
if (x<=mid)
{
i->lc=new node(i->l, mid);
upd2(em->lc, pre->lc, i->lc, x);
i->rc=em->rc;
}
else
{
i->lc=pre->lc;
i->rc=new node(mid+1, i->r);
upd2(em->rc, pre->rc, i->rc, x);
}
i->val=min(i->lc->val, i->rc->val);
}
void upd3(node *em, node *pre, node *i, int x)
{
if (i->l==i->r)
return;
int mid=(i->l+i->r)/2;
if (x<=mid)
{
i->lc=new node(i->l, mid);
upd3(em->lc, pre->lc, i->lc, x);
i->rc=pre->rc;
}
else
{
i->lc=em->lc;
i->rc=new node(mid+1, i->r);
upd3(em->rc, pre->rc, i->rc, x);
}
i->val=min(i->lc->val, i->rc->val);
}
int dist(int x, int y)
{
return abs(points[x].first-points[y].first)+abs(points[x].second-points[y].second);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, cur;
cin >> n >> k;
for (int i=1; i<=n; i++)
cin >> points[i].first >> points[i].second;
sort(points+1, points+n+1);
for (int i=1; i<=n; i++)
vec.push_back({-points[i].second, i});
sort(vec.begin(), vec.end());
empt=lft[0]=rght[0]=new node(1, n);
build(empt);
for (int i=1; i<=n; i++)
{
int x=vec[i-1].second;
lft[i]=new node(1, n);
rght[i]=new node(1, n);
upd1(lft[i-1], lft[i], x, points[x].second-points[x].first);
upd1(rght[i-1], rght[i], x, points[x].first+points[x].second);
root[i*2-1]=new node(1, n);
root[i*2]=new node(1, n);
upd2(empt, lft[i-1], root[i*2-1], x);
upd3(empt, rght[i-1], root[i*2], x);
lvers[x]=i*2-1;
rvers[x]=i*2;
if ((root[i*2-1]->val).first<1e15)
{
int y=(root[i*2-1]->val).second;
s.insert({dist(x, y), {x, y}});
//cout << "left x y " << x << ' ' << y << '\n';
}
if ((root[i*2]->val).first<1e15)
{
int y=(root[i*2]->val).second;
s.insert({dist(x, y), {x, y}});
//cout << "right x y " << x << ' ' << y << '\n';
}
}
cur=n*2;
while (k--)
{
cout << (s.begin()->first) << '\n';
int x=(s.begin()->second).first, y=(s.begin()->second).second;
//cout << "s element " << (s.begin()->first) << ' ' << x << ' ' << y << '\n';
s.erase(s.begin());
if (x<y)
{
cur++;
root[cur]=new node(1, n);
upd1(root[rvers[x]], root[cur], y, 1e18);
rvers[x]=cur;
if ((root[cur]->val).first<1e15)
{
y=(root[cur]->val).second;
s.insert({dist(x, y), {x, y}});
//cout << "new right x y " << x << ' ' << y << '\n';
}
}
else
{
cur++;
root[cur]=new node(1, n);
upd1(root[lvers[x]], root[cur], y, 1e18);
lvers[x]=cur;
if ((root[cur]->val).first<1e15)
{
y=(root[cur]->val).second;
s.insert({dist(x, y), {x, y}});
//cout << "new left x y " << x << ' ' << y << '\n';
}
}
}
}
