#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
#define f first
#define s second
using namespace std;
const int mxn = 2e6+5;
const ll inf = 1e15;
pii PP = {inf, -1};
struct node
{
node *left,*right;
pii val;
node(pii _v = PP, node *l = NULL, node *r = NULL) : val(_v), left(l), right(r){};
node *update(int l,int r,int p,ll v) {
if(l > p || r < p) return this;
if(l == r) {
return new node({v, l});
}
int mid = l + r >> 1;
node *ret = new node();
if(left == NULL) left = new node();
if(right == NULL) right = new node();
ret-> left = left-> update(l, mid, p, v);
ret-> right = right-> update(mid + 1, r, p, v);
ret-> val = min(ret-> left -> val, ret-> right -> val);
return ret;
}
pii query(int l,int r, int s, int t) {
if(l > t || r < s) return {inf,-1};
if(l >= s && r <= t) return val;
int mid = l + r >> 1;
if(left == NULL) left = new node();
if(right == NULL) right = new node();
return min(left-> query(l, mid, s, t), right-> query(mid + 1, r, s, t));
}
}*root1[mxn], *root2[mxn];
int pos[mxn], inv[mxn];
int n,k;
vector<pair<int,int>> pnt;
int main() {
cin >> n >> k;
root1[0] = new node(PP, new node(), new node());
root2[0] = new node(PP, new node(), new node());
vector<pair<int,int>> vv;
for(int i = 1; i <= n; i++) {
int x,y;
assert(scanf("%d %d",&x,&y));
vv.emplace_back(y, x);
pnt.emplace_back(x, y);
}
sort(pnt.begin(), pnt.end());
pnt.insert(pnt.begin(), {0,0});
sort(vv.begin(),vv.end());
priority_queue< tuple<ll,int, int, int> > pq;
for(int i = 1; i <= n; i++) {
auto [x,y] = pnt[i];
pos[i] = lower_bound(vv.begin(), vv.end(), make_pair(y, x)) - vv.begin() + 1;
inv[pos[i]] = i;
pii ed1 = root1[i - 1]-> query(1, n, pos[i] + 1, n);
pii ed2 = root2[i - 1]-> query(1, n, 1, pos[i] - 1);
pq.push({-(ed1.f + x - y), pos[i], ed1.s, 1});
pq.push({-(ed2.f + x + y), pos[i], ed2.s, -1});
root1[i] = root1[i - 1]-> update(1, n, pos[i], y - x);
root2[i] = root2[i - 1]-> update(1, n, pos[i], - y - x);
}
while(k--) {
auto [dist, u, v, tp] = pq.top();
pq.pop();
dist = -dist;
u = inv[u];
v = inv[v];
printf("%lld\n", dist);
if(tp == 1) {
root1[u] = root1[u]-> update(1, n, pos[v], inf);
pii ed = root1[u]-> query(1, n, pos[u] + 1, n);
auto [x,y] = pnt[u];
pq.push({-(ed.f + x - y), pos[u], ed.s, 1});
} else {
root2[u] = root2[u]-> update(1, n, pos[v], inf);
pii ed = root2[u]-> query(1, n, 1, pos[u] - 1);
auto [x,y] = pnt[u];
pq.push({-(ed.f + x + y), pos[u], ed.s, -1});
}
}
}
