#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define BIT(mask, x) ((mask >> (x)) & 1)
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug(__VA_ARGS__)
template<typename T> void debug(T x) { cerr << x << "\n"; }
template<typename T, typename... Args> void debug(T x, Args... args) {
cerr << x << ", "; debug(args...);
}
// -------------------------------------- CON CUA BO HCN --------------------------------------
const int maxn = 2.5e5 + 3;
int n, K, id[maxn], m;
pll a[maxn];
pll ids[maxn];
// --------------------------------------------------------------------------------------------
struct Node
{
int l, r; pll val;
Node() {l = r = 0; val.first = val.second = 1e18;}
};
struct PerSeg
{
vector<Node> seg; int curNode;
vector<int> root;
void init(int _n) {seg.resize(70 * max(_n, K)); root.assign(n + 1, 0); curNode = 0;}
void upd(int id, int l, int r, int pos, ll val)
{
if (l == r)
{
return void(seg[id].val = {val, l});
}
int mid = l + r >> 1;
if (pos <= mid)
{
seg[++curNode] = seg[seg[id].l];
seg[id].l = curNode;
upd(curNode, l, mid, pos, val);
}
else
{
seg[++curNode] = seg[seg[id].r];
seg[id].r = curNode;
upd(curNode, mid + 1, r, pos, val);
}
seg[id].val = min(seg[seg[id].l].val, seg[seg[id].r].val);
}
pll get(int id, int l, int r, int u, int v)
{
if (l > r || l > v || r < u) return {ll(1e18), ll(1e18)};
if (l >= u && r <= v) return seg[id].val;
int mid = l + r >> 1 ;
return min(get(seg[id].l, l, mid, u, v), get(seg[id].r, mid + 1, r, u, v));
}
} segLowerL, segLowerR;
ll get_ans(const int &pos)
{
pll x = segLowerL.get(segLowerL.root[pos], 1, m, 1, id[pos]);
pll y = segLowerR.get(segLowerR.root[pos], 1, m, id[pos] + 1, m);
if (x.first == 1e18 && y.first == 1e18) return 1e18;
// if (x.first < 0)
x.first += a[pos].first + a[pos].second;
y.first += a[pos].first - a[pos].second;
// dbg(pos);
// dbg(x.first, x.second);
// dbg(y.first, y.second);
if (x.first <= y.first)
{
segLowerL.upd(segLowerL.root[pos], 1, m, x.second, 1e18);
return x.first;
}
segLowerR.upd(segLowerR.root[pos], 1, m, y.second, 1e18);
return y.first;
}
void solve()
{
cin >> n >> K;
FOR(i, 1, n) cin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1);
FOR(i, 1, n) ids[i] = {a[i].second, i};
sort(ids + 1, ids + n + 1);
m = n;
segLowerL.init(m); segLowerR.init(m);
priority_queue<pll, vector<pll>, greater<pll>> pq;
FOR(i, 1, n)
{
segLowerL.root[i] = ++segLowerL.curNode;
segLowerR.root[i] = ++segLowerR.curNode;
segLowerL.seg[segLowerL.curNode] = segLowerL.seg[segLowerL.root[i - 1]];
segLowerR.seg[segLowerR.curNode] = segLowerR.seg[segLowerR.root[i - 1]];
id[i] = lower_bound(ids + 1, ids + n + 1, pll(a[i].second, i)) - ids;
if (i > 1) segLowerL.upd(segLowerL.root[i], 1, m, id[i - 1], - a[i - 1].first - a[i - 1].second);
if (i > 1) segLowerR.upd(segLowerR.root[i], 1, m, id[i - 1], - a[i - 1].first + a[i - 1].second);
}
FOR(i, 2, n)
{
ll cur = get_ans(i);
if (cur != 1e18) pq.push({cur, i});
}
// cerr << segLowerL.get(segLowerL.root[3], 1, m, 1, 1).first << '\n';
// cerr << "NEXT\n\n";
// cerr << get_ans(3) << '\n';
// cerr << get_ans(3) << '\n';
while (K--)
{
pll cur = pq.top(); pq.pop();
ll nxt = get_ans((int)cur.second);
cout << cur.first << '\n';
if (nxt != 1e18) pq.push({nxt, cur.second});
}
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define TASK "TEST"
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
solve();
return 0;
}
/* NOTES:
*/
