#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 3e5;
pair <long long int, long long int> a[maxn];
pair <long long int, long long int> b[maxn];
set <pair <long long int, long long int>> s;
long long int p[maxn];
vector <long long int> ans1, ans2;
bool is_ar(long long int i, long long int j)
{
return a[j].first >= a[i].first and a[j].second >= a[i].second;
}
bool is_br(long long int i, long long int j)
{
return a[j].first > a[i].first and a[j].second < a[i].second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long int n, k;
cin >> n >> k;
for (long long int i = 1;i <= n;i++)
{
cin >> a[i].first >> a[i].second;
}
b[n + 1] = {2e14, n + 1};
a[n + 1] = {1e9 + 10, 1e9 + 10};
for (long long int i = 1;i <= n;i++)
{
b[i] = {a[i].first + a[i].second, i};
}
sort(b + 1, b + 1 + n);
for (long long int i = 1;i <= n;i++)
{
p[i] = i + 1;
while (!is_ar(b[i].second, b[p[i]].second))
{
p[i]++;
}
s.insert({b[p[i]].first - b[i].first, i});
}
int q = k;
while (q-- and (*s.begin()).first <= 4e9)
{
ans1.push_back((*s.begin()).first);
int i = (*s.begin()).second;
s.erase(s.begin());
p[i]++;
while (!is_ar(b[i].second, b[p[i]].second))
{
p[i]++;
}
s.insert({b[p[i]].first - b[i].first, i});
}
s.clear();
a[n + 1] = {1e9 + 10, -1e9 - 10};
for (long long int i = 1;i <= n;i++)
{
b[i] = {a[i].first - a[i].second, i};
}
sort(b + 1, b + 1 + n);
for (long long int i = 1;i <= n;i++)
{
p[i] = i + 1;
while (!is_br(b[i].second, b[p[i]].second))
{
p[i]++;
}
s.insert({b[p[i]].first - b[i].first, i});
}
q = k;
while (q-- and (*s.begin()).first <= 4e9)
{
ans2.push_back((*s.begin()).first);
int i = (*s.begin()).second;
s.erase(s.begin());
p[i]++;
while (!is_br(b[i].second, b[p[i]].second))
{
p[i]++;
}
s.insert({b[p[i]].first - b[i].first, i});
}
ans1.push_back(1e13);
ans2.push_back(1e13);
int pt1 = 0, pt2 = 0;
for (int i = 1;i <= k;i++)
{
if (ans1[pt1] < ans2[pt2])
{
cout << ans1[pt1++] << '\n';
}
else
{
cout << ans2[pt2++] << '\n';
}
}
}
