// made by Tima
// 2025 will be a golden year...
//BREAK YOUR LIMITS!!!!
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define int long long
#define F first
#define S second
#define y1 SBIL
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <pair <int,int> , int>
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5 , M = 1e6 + 5;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,k,x[N],y[N],root[M],y1[N],val[3][N],timer;
pii p[N];
tpii br[N];
struct node{
int x,i,l,r;
}t[200 * N];
void build(int &v , int tl = 1 , int tr = n){
if(!v) v = ++ timer;
if(tl == tr){
t[v].x = INF;
t[v].i = tl;
return;
}
int tm = tl + tr >> 1;
build(t[v].l , tl , tm);
build(t[v].r , tm + 1 , tr);
t[v].x = min(t[t[v].l].x , t[t[v].r].x);
}
void upd(int nv , int &v , int pos , int x , int tl = 1 , int tr = n){
if(!v) v = ++ timer;
if(tl == tr){
// cout << tl << ' ' << x << '\n';
t[v].x = x;
t[v].i = tl;
return;
}
int tm = tl + tr >> 1;
if(pos <= tm){
t[v].r = t[nv].r;
upd(t[nv].l , t[v].l , pos , x , tl , tm);
}
else{
t[v].l = t[nv].l;
upd(t[nv].r , t[v].r , pos , x , tm + 1 , tr);
}
if(t[t[v].l].x <= t[t[v].r].x){
t[v].i = t[t[v].l].i;
}
else{
t[v].i = t[t[v].r].i;
}
t[v].x = min(t[t[v].l].x , t[t[v].r].x);
// cout << " v -- > " << v << ' ' << tl << ' ' << tr << ' ' << t[v].x << ' ' << t[v].i << '\n';
}
pii get(int v , int l , int r , int tl = 1 , int tr = n){
if(tl > r || tr < l) return {INF , INF};
if(tl >= l && tr <= r) return {t[v].x , t[v].i};
int tm = tl + tr >> 1;
return min(get(t[v].l , l , r , tl , tm) , get(t[v].r , l , r , tm + 1 , tr));
}
void Gold(){
cin >> n >> k;
set <int> st1;
map <int,int> mp,last;
map <int,int> mp1;
for(int i = 1 ; i <= n ; i++){
cin >> x[i] >> y[i];
p[i] = {y[i] , x[i]};
}
sort(p + 1 , p + n + 1);
for(int i = 1 ; i <= n ; i++){
x[i] = p[i].S , y[i] = p[i].F;
br[i] = {{x[i] , y[i]} , i};
}
sort(br + 1 , br + n + 1);
for(int i = 1 ; i <= n ; i++){
x[i] = br[i].F.F , y[i] = br[i].F.S , y1[i] = br[i].S;
// cout << x[i] << ' ' << y[i] << ' ' << y1[i] << '\n';
}
// cout << '\n';
int cnt = 1;
// 1 pers
build(root[1]);
multiset <pair <pii , pii>> st;
val[1][1] = 1;
for(int i = 2 ; i <= n ; i++){
++cnt;
upd(root[cnt - 1] , root[cnt] , y1[i - 1] , y[i - 1] - x[i - 1]);
// cout << "DO\n";
val[1][i] = cnt;
pii b = get(root[cnt] , y1[i] + 1 , n);
st.insert({{b.F + x[i] - y[i] , b.S} , {i , 1}});
}
// 2 pers
build(root[++cnt]);
val[2][1] = cnt;
for(int i = 2 ; i <= n ; i++){
++cnt;
upd(root[cnt - 1] , root[cnt] , y1[i - 1] , -x[i - 1] - y[i - 1]);
val[2][i] = cnt;
pii b = get(root[cnt] , 1 , y1[i] - 1);
// cout << i << ' ' << b.F << ' ' << b.S << ' ' << x[i] + y[i] << '\n';
st.insert({{b.F + x[i] + y[i] , b.S} , {i , 2}});
}
while(k--){
pair <pii , pii> th = *st.begin();
int i = th.S.F , d = th.F.F , yj = th.F.S , tp = th.S.S;
cout << d << '\n';
upd(root[val[tp][i]] , root[++cnt] , yj , INF);
val[tp][i] = cnt;
if(tp == 1){
pii b = get(root[cnt] , y1[i] + 1 , n);
st.insert({{b.F + x[i] - y[i] , b.S} , {i , 1}});
}
else{
pii b = get(root[cnt] , 1 , y1[i] - 1);
st.insert({{b.F + x[i] + y[i] , b.S} , {i , 2}});
}
st.erase(st.find(th));
}
}
signed main(/*Zhunussov Temirlan*/){
//freopen("txt.in","r",stdin);freopen("txt.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);
srand(time(0));
int TT = 1;
// cin >> TT;
for(int i = 1 ; i <= TT ; i++){
//cout << "Case " << i << ": ";
Gold();
}
}
