/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;
pair<ll, int> f(pair<ll, int> x, pair<ll, int> y){
if(x.ff < y.ff) return x;
if(y.ff < x.ff) return y;
return (x.ss < y.ss) ? x : y;
}
struct Node{
Node *L, *R;
pair<ll, int> mn = {INF, -1};
int idx;
Node(){
L=R=nullptr;
idx = -1;
}
Node(Node *l, Node *r){
L = l, R = r;
mn = f((L ? L->mn : mn), (R ? R->mn : mn));
}
Node(ll val, int idx){
mn = {val, idx};
}
};
Node *build(int l, int r){
if(l == r){
return new Node();
}
int m = l+r>>1;
return new Node(build(l, m), build(m+1, r));
}
Node* upd(Node *v, int l, int r, int p, ll val){
if(l == r){
if(val == -INF){
return new Node();
}
return new Node(val, l);
}
int m = l+r>>1;
if(p <= m){
return new Node(upd(v->L, l, m, p, val), v->R);
}
return new Node(v->L, upd(v->R, m+1, r, p, val));
}
pair<ll, int> get(Node *v, int l, int r, int ql, int qr){
if(l > qr || ql > r) return pair<ll, int>{INF, -1};
if(ql <= l && r <= qr){
return v->mn;
}
int m = l+r>>1;
return f(
get(v->L, l, m, ql, qr),
get(v->R, m+1, r, ql, qr)
);
}
int n, k;
array<int, 3> a[N], b[N];
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i][0] >> a[i][1];
a[i][2] = i;
}
for(int i = 1; i <= n; ++i){
b[i][0] = a[i][1];
b[i][1] = a[i][0];
b[i][2] = i;
}
sort(b+1, b+1+n); // y positions
for(int i = 1; i <= n; ++i) a[b[i][2]][2] = i;
sort(a+1, a+1+n);
vector<Node*> T1, T2;
T1.pb(build(1, n));
T2.pb(build(1, n));
// for(int i = 1; i <= n; ++i){
// cout << a[i][0] << ' ' << a[i][1] << ' ' << a[i][2] << '\n';
// }
priority_queue<array<ll, 3>> Q;
for(int i = 1; i <= n; ++i){
auto L = get(T1.back(), 1, n, 1, a[i][2] - 1);
auto R = get(T2.back(), 1, n, a[i][2] + 1, n);
L.ff += a[i][0] + a[i][1];
R.ff += a[i][0] - a[i][1];
auto res = f(L, R);
if(res.ss != -1){
Q.push({-res.ff, i, res.ss});
}
// cout << L.ff << ' ' << L.ss << '\n';
T1.pb(upd(T1.back(), 1, n, a[i][2], -a[i][1]-a[i][0]));
T2.pb(upd(T2.back(), 1, n, a[i][2], a[i][1]-a[i][0]));
}
while(k--){
auto [val, v, idx] = Q.top(); Q.pop();
// cout << v << ' ' << idx << ' ';
cout << -val << '\n';
T1[v - 1] = upd(T1[v - 1], 1, n, idx, -INF);
T2[v - 1] = upd(T2[v - 1], 1, n, idx, -INF);
auto L = get(T1[v - 1], 1, n, 1, a[v][2] - 1);
auto R = get(T2[v - 1], 1, n, a[v][2] + 1, n);
L.ff += a[v][0] + a[v][1];
R.ff += a[v][0] - a[v][1];
auto res = f(L, R);
if(res.ss != -1){
Q.push({-res.ff, v, res.ss});
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
