#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 250'000;
const int S = 10'000'000;
const ll INF = 1'000'000'000'000'000'000;
int n, k;
pair<ll, ll> p[N + 10];
int counter, r1[N + 10], r2[N + 10];
int root1, root2, tmp[N + 10];
int lft[S + 10], rght[S + 10];
pair<ll, int> seg[S + 10];
set<pair<ll, int>> s;
ll ans[N + 10];
void readInput() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> p[i].second >> p[i].first;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)
swap(p[i].first, p[i].second);
}
pair<ll, int> get(int st, int en, int id, int l = 1, int r = n + 1) {
if (en <= l || r <= st)
return {INF, 0};
if (st <= l && r <= en)
return seg[id];
int mid = (l + r) >> 1;
return min(get(st, en, lft[id], l, mid), get(st, en, rght[id], mid, r));
}
int copyVer(int id) {
int u = ++counter;
lft[u] = lft[id];
rght[u] = rght[id];
seg[u] = seg[id];
return u;
}
int update(int idx, ll val, int id, int l = 1, int r = n + 1) {
if (idx < l || r <= idx)
return id;
id = copyVer(id);
if (l + 1 == r) {
seg[id] = {val, l};
return id;
}
int mid = (l + r) >> 1;
lft[id] = update(idx, val, lft[id], l, mid);
rght[id] = update(idx, val, rght[id], mid, r);
seg[id] = min(seg[lft[id]], seg[rght[id]]);
return id;
}
void build(int id, int l = 1, int r = n + 1) {
if (l + 1 == r) {
seg[id] = {INF, l};
return;
}
lft[id] = ++counter;
rght[id] = ++counter;
int mid = (l + r) >> 1;
build(lft[id], l, mid);
build(rght[id], mid, r);
seg[id] = min(seg[lft[id]], seg[rght[id]]);
}
void calcBase() {
counter = 1;
root1 = root2 = 1;
build(1);
}
void calcR() {
vector<pair<ll, int>> vec;
for (int i = 1; i <= n; i++)
vec.push_back({p[i].first, i});
sort(vec.begin(), vec.end());
for (auto [val, i]: vec) {
root1 = update(i, p[i].second - p[i].first, root1);
root2 = update(i, -p[i].second - p[i].first, root2);
r1[i] = root1;
r2[i] = root2;
}
}
void calcNext(int i) {
if (tmp[i]) {
r1[i] = update(tmp[i], INF, r1[i]);
r2[i] = update(tmp[i], INF, r2[i]);
}
pair<ll, int> res1 = get(i + 1, n + 1, r1[i]);
pair<ll, int> res2 = get(1, i, r2[i]);
res1.first += p[i].first - p[i].second;
res2.first += p[i].first + p[i].second;
pair<ll, int> res = min(res1, res2);
s.insert({res.first, i});
tmp[i] = res.second;
}
void init() {
for (int i = 1; i <= n; i++)
calcNext(i);
}
void calcAns() {
for (int i = 1; i <= k; i++) {
pair<ll, int> tmp = *s.begin();
s.erase(s.begin());
cout << tmp.first << '\n';
calcNext(tmp.second);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcBase();
calcR();
init();
calcAns();
return 0;
}
