/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3e5 + 10;
int n, k, ridx[maxn];
ll x[maxn], y[maxn], bef[maxn], nxt[maxn];
struct element
{
int idx;
ll sum;
element()
{
idx = 0;
sum = 0;
}
element(int _idx, ll _sum)
{
idx = _idx;
sum = _sum;
}
bool operator < (const element &e) const
{
return sum > e.sum;
}
};
bool cmp(int idx1, int idx2)
{
if (x[idx1] < x[idx2])
return true;
if (x[idx1] > x[idx2])
return false;
return y[idx1] < y[idx2];
}
struct node
{
ll up, low;
};
node tree[maxn * 4];
node merge_node(node nd1, node nd2)
{
node nd;
nd.up = min(nd1.up, nd2.up);
nd.low = min(nd1.low, nd2.low);
return nd;
}
void clear_tree(int root, int left, int right)
{
if (left == right)
{
tree[root].up = tree[root].low = 1e18;
return;
}
int mid = (left + right) / 2;
clear_tree(root * 2, left, mid);
clear_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int idx, node upd)
{
if (left == right)
{
tree[root] = merge_node(tree[root], upd);
return;
}
int mid = (left + right) / 2;
if (idx <= mid)
update(root * 2, left, mid, idx, upd);
else
update(root * 2 + 1, mid + 1, right, idx, upd);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
if (left >= qleft && right <= qright)
return tree[root];
if (left > qright || right < qleft)
return {(ll)1e18, (ll)1e18};
int mid = (left + right) / 2;
return merge_node(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
void solve()
{
cin >> n >> k;
bool y0 = true;
for (int i = 1; i <= n; i ++)
{
cin >> x[i] >> y[i];
if (y[i] != 0)
y0 = false;
}
if (n <= 1000)
{
vector < ll > v;
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
{
v.push_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
}
sort(v.begin(), v.end());
for (int i = 0; i < k; i ++)
cout << v[i] << endl;
}
else if (y0 == true)
{
sort(x + 1, x + n + 1);
priority_queue < element > pq;
for (int i = 1; i <= n; i ++)
{
bef[i] = i - 1;
if (i != 1)
{
element e;
e.sum = x[i] - x[i - 1];
e.idx = i;
pq.push(e);
}
}
for (int q = 0; q < k; q ++)
{
element e = pq.top();
pq.pop();
cout << e.sum << endl;
bef[e.idx] --;
if (bef[e.idx] != 0)
{
e.sum = x[e.idx] - x[bef[e.idx]];
pq.push(e);
}
}
}
else if (k == 1)
{
for (int i = 1; i <= n; i ++)
ridx[i] = i;
sort(ridx + 1, ridx + n + 1, cmp);
set < ll > stx, sty;
map < ll, int > revx, revy;
for (int i = 1; i <= n; i ++)
{
stx.insert(x[i]);
sty.insert(y[i]);
}
int cntx = 0;
for (int v : stx)
revx[v] = ++ cntx;
int cnty = 0;
for (int v : sty)
revy[v] = ++ cnty;
clear_tree(1, 1, cnty);
ll ans = 1e18;
for (int i = 1; i <= n; i ++)
{
int idx = ridx[i];
node nd1 = query(1, 1, cnty, 1, revy[y[idx]]);
node nd2 = query(1, 1, cnty, revy[y[idx]], cnty);
ll sum = min(nd1.low + x[idx] + y[idx], nd2.up + x[idx] - y[idx]);
ans = min(ans, sum);
node nd;
nd.low = - x[idx] - y[idx];
nd.up = - x[idx] + y[idx];
update(1, 1, cnty, revy[y[idx]], nd);
}
cout << ans << endl;
}
}
int main()
{
solve();
return 0;
}
