#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
const int MAXLOG = 20;
int n, k;
struct PersistentSegmentTree
{
struct Node
{
llong min;
int minIdx;
int left, right;
Node()
{
min = INF;
minIdx = left = right = 0;
}
void assign(const Node &left, const Node &right)
{
if (left.min < right.min)
{
min = left.min;
minIdx = left.minIdx;
} else
{
min = right.min;
minIdx = right.minIdx;
}
}
friend Node operator + (const Node &left, const Node &right)
{
if (left.min < right.min)
{
return left;
} else
{
return right;
}
}
};
Node tree[2 * MAXN * MAXLOG];
int cnt;
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].minIdx = l;
return;
}
int mid = (l + r) / 2;
tree[node].left = ++cnt;
tree[node].right = ++cnt;
build(l, mid, tree[node].left);
build(mid + 1, r, tree[node].right);
tree[node].assign(tree[tree[node].left], tree[tree[node].right]);
}
void update(int l, int r, int newNode, int oldNode, int queryPos, llong queryVal)
{
tree[newNode] = tree[oldNode];
if (l == r)
{
tree[newNode].min = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid)
{
tree[newNode].left = ++cnt;
update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
} else
{
tree[newNode].right = ++cnt;
update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
}
tree[newNode].assign(tree[tree[newNode].left], tree[tree[newNode].right]);
}
Node query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node res;
int mid = (l + r) / 2;
if (queryL <= mid) res = query(l, mid, tree[node].left, queryL, queryR);
if (mid + 1 <= queryR) res = res + query(mid + 1, r, tree[node].right, queryL, queryR);
return res;
}
void build()
{
cnt = 1;
build(1, n, 1);
}
int update(int oldNode, int pos, llong val)
{
int newNode = ++cnt;
update(1, n, cnt, oldNode, pos, val);
return newNode;
}
Node query(int node, int l, int r)
{
return query(1, n, node, l, r);
}
};
struct Point
{
llong x, y;
friend bool operator < (const Point &a, const Point &b)
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
};
struct PQelement
{
llong value;
char type;
int updIdx;
int myIdx;
friend bool operator < (const PQelement &a, const PQelement &b)
{
return a.value > b.value;
}
};
Point p[MAXN];
int perm[MAXN];
int inPerm[MAXN];
PersistentSegmentTree treePlus;
PersistentSegmentTree treeMinus;
std::priority_queue <PQelement> pq;
int nodePlus[MAXN];
int nodeMinus[MAXN];
void solve()
{
std::sort(p + 1, p + 1 + n);
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int a, int b)
{
return p[a].y < p[b].y;
});
for (int i = 1 ; i <= n ; ++i)
{
inPerm[perm[i]] = i;
}
treePlus.build();
treeMinus.build();
nodePlus[n] = nodeMinus[n] = 1;
for (int i = n - 1 ; i >= 1 ; --i)
{
nodePlus[i] = treePlus.update(nodePlus[i + 1], inPerm[i + 1], p[i + 1].x + p[i + 1].y);
nodeMinus[i] = treeMinus.update(nodeMinus[i + 1], inPerm[i + 1], p[i + 1].x - p[i + 1].y);
PersistentSegmentTree::Node plusRes = treePlus.query(nodePlus[i], inPerm[i], n);
if (plusRes.min != INF)
{
plusRes.min += -p[i].x - p[i].y;
pq.push({plusRes.min, '+', plusRes.minIdx, i});
}
PersistentSegmentTree::Node minusRes = treeMinus.query(nodeMinus[i], 1, inPerm[i]);
if (minusRes.min != INF)
{
minusRes.min += -p[i].x + p[i].y;
pq.push({minusRes.min, '-', minusRes.minIdx, i});
}
}
for (int time = 0 ; time < k ; ++time)
{
assert(pq.size());
auto [val, type, updIdx, idx] = pq.top();
pq.pop();
std::cout << val << '\n';
if (type == '+')
{
nodePlus[idx] = treePlus.update(nodePlus[idx], updIdx, INF);
PersistentSegmentTree::Node plusRes = treePlus.query(nodePlus[idx], inPerm[idx], n);
if (plusRes.min != INF)
{
plusRes.min += -p[idx].x - p[idx].y;
pq.push({plusRes.min, '+', plusRes.minIdx, idx});
}
} else
{
nodeMinus[idx] = treeMinus.update(nodeMinus[idx], updIdx, INF);
PersistentSegmentTree::Node minusRes = treeMinus.query(nodeMinus[idx], 1, inPerm[idx]);
if (minusRes.min != INF)
{
minusRes.min += -p[idx].x + p[idx].y;
pq.push({minusRes.min, '-', minusRes.minIdx, idx});
}
}
}
}
void input()
{
std::cin >> n >> k;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> p[i].x >> p[i].y;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
