//
// Created by liasa on 09/03/2026.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>
#define tpl tuple<ll, ll, ll>
const ll inf = 1e18;
struct Seg {
Seg *left = nullptr, *right = nullptr;
int l, r, mid;
pll mn = {inf, -1};
Seg(int l, int r) : l(l), r(r), mid((l + r) / 2) {}
Seg(Seg *copy) {
left = copy->left, right = copy->right, mid = copy->mid, l = copy->l,
r = copy->r, mn = copy->mn;
}
void ensure() {
if (l == r)
return;
if (left == nullptr) {
left = new Seg(l, mid);
right = new Seg(mid + 1, r);
}
}
pll q(int a, int b) {
if (l > b || r < a)
return {inf, -1};
if (l >= a && r <= b)
return mn;
ensure();
return min(left->q(a, b), right->q(a, b));
}
Seg *update(Seg *node, int pos, pll new_val) {
Seg *cur = new Seg(node);
if (cur->l == cur->r) { // the leaf node
cur->mn = min(cur->mn, new_val);
return cur;
}
cur->ensure();
if (pos <= cur->mid)
cur->left = update(cur->left, pos, new_val);
else
cur->right = update(cur->right, pos, new_val);
cur->mn = min(cur->left->mn, cur->right->mn);
return cur;
}
};
Seg *build(int l, int r) {
Seg *node = new Seg(l, r);
if (l != r) {
node->left = build(l, node->mid);
node->right = build(node->mid + 1, r);
}
return node;
}
vector<long long> ShortestWalkways(int n, int k, vector<int> X, vector<int> Y) {
v<tpl> vec;
v<ll> vals, ans;
lp(i, 0, n) {
vec.push_back({X[i], Y[i], i});
vals.push_back(Y[i]);
}
sort(vec.begin(), vec.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
v<int> y_id(n), prev_same(n, -1), last_same(m, -1);
lp(i, 0, n) {
auto [x, y, id] = vec[i];
y_id[i] = lower_bound(vals.begin(), vals.end(), y) - vals.begin();
prev_same[i] = last_same[y_id[i]];
last_same[y_id[i]] = i;
}
v<Seg *> low(n + 1), high(n + 1);
low[0] = high[0] = build(0, m - 1);
lp(i, 1, n + 1) {
auto [x, y, id] = vec[i - 1];
int p = y_id[i - 1];
low[i] = low[i - 1]->update(low[i - 1], p, {-(x + y), i - 1});
high[i] = high[i - 1]->update(high[i - 1], p, {-(x - y), i - 1});
}
struct State {
ll dis;
int a, t, l, r, b;
bool operator>(const State &o) const { return dis > o.dis; }
};
priority_queue<State, v<State>, greater<State>> pq;
auto add = [&](int a, int t, int l, int r) {
if (l > r)
return;
auto [x, y, id] = vec[a];
pll q = (t ? high[a] : low[a])->q(l, r);
if (q.second == -1)
return;
pq.push({(t ? x - y : x + y) + q.first, a, t, l, r, (int)q.second});
};
auto same = [&](int a, int b) {
b = prev_same[b];
if (b == -1 || b >= a)
return;
auto [ax, ay, id1] = vec[a];
auto [bx, by, id2] = vec[b];
pq.push({llabs(ax - bx) + llabs(ay - by), a, 0, y_id[b], y_id[b], b});
};
lp(a, 1, n) {
add(a, 0, 0, y_id[a]);
add(a, 1, y_id[a] + 1, m - 1);
}
lp(j, 0, k) {
auto [dis, a, t, l, r, b] = pq.top();
pq.pop();
ans.push_back(dis);
int p = y_id[b];
add(a, t, l, p - 1);
add(a, t, p + 1, r);
same(a, b);
}
return ans;
}
// #ifndef EVAL
int readInt() {
int i;
if (scanf("%d", &i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return i;
}
int main() {
std::ios_base::sync_with_stdio(0);
int N, K;
N = readInt();
K = readInt();
std::vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
X[i] = readInt();
Y[i] = readInt();
}
std::vector<long long> ans = ShortestWalkways(N, K, X, Y);
for (int i = 0; i < ans.size(); i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
// #endif
