// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 250005;

typedef pair<LL, LL> PLL;

int n, k;

PLL e[N];

LL X, d[N], t;

bool inline cmp2(PLL x, PLL y) {
	return x.se < y.se;
}

priority_queue<LL> Q;

vector<LL> B;

PLL h[N];

void inline mg(int l, int mid, int r) {
	for (int k = l, i = l, j = mid + 1; k <= r; k++) {
		if (j > r || (i <= mid && e[i].se < e[j].se)) h[k] = e[i++];
		else h[k] = e[j++];
	}
	for (int k = l; k <= r; k++) e[k] = h[k];
}

void cdq(int l, int r) {
	if (l >= r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	while (Q.size()) Q.pop();
	for (int i = mid + 1, j = l; i <= r; i++) {
		if (t == k) break;
		while (j <= mid && e[j].se <= e[i].se) {
			Q.push(e[j].fi + e[j].se);
			j++;
		}
		B.clear();
		while (t < k && !Q.empty() && e[i].fi + e[i].se - Q.top() <= X) {
			B.pb(Q.top()); 
			d[++t] = e[i].fi + e[i].se - Q.top();
			Q.pop();
		}
		while (B.size()) Q.push(B.back()), B.pop_back();
	}
	while (Q.size()) Q.pop();
	for (int i = r, j = mid; i > mid; i--) {
		if (t == k) break;
		while (j >= l && e[j].se > e[i].se) {
			Q.push(e[j].fi - e[j].se);
			j--;
		}
		B.clear();
		while (t < k && !Q.empty() && e[i].fi - e[i].se - Q.top() <= X) {
			B.pb(Q.top()); 
			d[++t] = e[i].fi - e[i].se - Q.top();
			Q.pop();
		}
		while (B.size()) Q.push(B.back()), B.pop_back();
	}
	mg(l, mid, r);
}

int inline chk() {
	sort(e + 1, e + 1 + n);
	t = 0;
	cdq(1, n);
	return t;
}

int main() {
	read(n), read(k);
	for (int i = 1; i <= n; i++) read(e[i].fi), read(e[i].se);
	LL l = 0, r = 4e9;
	while (l < r) {
		LL mid = (l + r) >> 1;
		X = mid;
		if (chk() >= k) r = mid;
		else l = mid + 1;
	}
	X = r - 1;
	chk();
	sort(d + 1, d + 1 + t);
	while (t < k) d[++t] = r;
	for (int i = 1; i <= k; i++)
		printf("%lld\n", d[i]);
    return 0;
}