// author : thembululquaUwU
// 3.9.2024
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair <int, int>;
using pli = pair <ll, int>;
using vi = vector <int>;
const int N = 3e5;
const int mod = 1e9 + 7;
void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fd(sr, x) (lower_bound(sr.begin(), sr.end(), x) - sr.begin())
#define uq(sr) (sr).erase(unique(all((sr))), (sr).end())
#define szv(v) (int((v).size()))
#define left __left__
#define right __right__
const pli inf = {1e12, -1};
int n, k;
struct Node {
Node *left, *right;
pli Min = inf;
Node (pli val){
left = nullptr; right = nullptr; Min = val;
}
Node (Node *left, Node *right){
this -> left = left;
this -> right = right;
this -> Min = min(left -> Min, right -> Min);
}
};
Node *T[2][N];
Node *build(int l = 0, int r = n - 1){
if (l == r) return new Node(inf);
int mid = l + r >> 1;
return new Node(build(l, mid), build(mid + 1, r));
}
Node *update(Node *old, int u, pli val, int l = 0, int r = n - 1){
if (l == r) return new Node(val);
auto &left = old -> left;
auto &right = old -> right;
int mid = l + r >> 1;
if (mid >= u) return new Node(update(left, u, val, l, mid), right);
return new Node(left, update(right, u, val, mid + 1, r));
}
pli get(Node *cur, int u, int v, int l = 0, int r = n - 1){
if (r < u || v < l) return inf;
if (u <= l && r <= v) return cur -> Min;
int mid = l + r >> 1;
return min(get(cur -> left, u, v, l, mid), get(cur -> right, u, v, mid + 1, r));
}
ll upd[2][N], qry[2][N], Min_pair[2][N];
pair <int, int> seg[2][N];
void solve(){
cin >> n >> k;
vector <ii> tower(n);
for (int i = 0; i < n; ++ i) cin >> tower[i].fi >> tower[i].se;
sort(all(tower)); vector <ii> sr;
for (int i = 0; i < n; ++ i) sr.pb({tower[i].se, i});
sort(all(sr)); uq(sr); vector <int> fake(n);
for (int t : {0, 1}) T[t][0] = build();
priority_queue <pair <pli, int>, vector <pair <pli, int>>, greater <pair <pli, int>>> qu;
for (int i = 0; i < n; ++ i) {
auto [X, Y] = tower[i];
fake[i] = fd(sr, ii(Y, i));
qry[0][i] = X + Y, qry[1][i] = X - Y;
for (int t : {0, 1}){
int u = 0, v = fake[i];
if (t) u = fake[i] + 1, v = n - 1;
seg[t][i] = ii(u, v);
if (u <= v){
auto [dist, idx] = get(T[t][i], u, v);
if (idx > -1){
qu.push({{dist + qry[t][i], i}, t});
Min_pair[t][i] = idx;
}
}
}
upd[0][i] = -X - Y, upd[1][i] = -X + Y;
for (int t : {0, 1}) T[t][i + 1] = update(T[t][i], fake[i], {upd[t][i], i});
}
while (k --){
auto [skf, t] = qu.top(); qu.pop();
auto [di, i] = skf; cout << di << endl;
int idxMin = Min_pair[t][i];
T[t][i] = update(T[t][i], fake[idxMin], inf);
auto [u, v] = seg[t][i];
if (u <= v){
auto [dist, idx] = get(T[t][i], u, v);
if (idx > -1){
qu.push({{dist + qry[t][i], i}, t});
Min_pair[t][i] = idx;
}
}
}
}
int main(){
if (fopen("pqh.inp", "r")){
freopen("pqh.inp", "r", stdin);
freopen("pqh.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t --) solve();
return 0;
}
