#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int inf = 1<<30;
int n, k;
vector<int> cd[2] = {{-inf, inf}, {-inf, inf}};
vector<array<int, 4>> cut(vector<array<int, 4>> rects, array<int, 2> p) {
for(int i = rects.size(); i--;) {
auto r = rects[i];
if(r[0] <= p[0] && p[0] <= r[2] && r[1] <= p[1] && p[1] <= r[3])
swap(rects[i], rects.back()), rects.pop_back();
}
return rects;
}
vector<array<int, 2>> solve(vector<array<int, 4>> rects, int k) {
if(k == 0) return {};
if(rects.empty()) return vector<array<int, 2>>(1, {1, 1});
array<int, 4> bounds;
bounds[2] = bounds[3] = 2*n + 2;
bounds[0] = bounds[1] = 0;
for(auto i : rects)
for(int j = 0; j < 4; j++)
bounds[j] = (j > 1 ? min(bounds[j], i[j]) : max(bounds[j], i[j]));
//cout << bounds[0] << " " << bounds[1] << " " << bounds[2] << " " << bounds[3] << endl;
if(bounds[0] <= bounds[2] || bounds[1] <= bounds[3]) {
int rev = 0;
if(bounds[0] > bounds[2]) {
swap(bounds[0], bounds[1]), swap(bounds[2], bounds[3]);
for(auto &i : rects)
swap(i[0], i[1]), swap(i[2], i[3]), rev = 1;
}
vector<array<int, 2>> segs, ans;
for(auto &i : rects) segs.push_back({i[1], i[3]});//, cout << i[0] << " " << i[1] << " " << i[2] << " " << i[3] << '\n';
sort(all(segs), greater<>());
int c = inf;
for(auto i : segs) {
//cout << i[0] << " " << i[1] << '\n';
if(i[1] < c) {
c = i[0];
ans.push_back(rev ? array<int, 2>{c, bounds[0]} : array<int, 2>{bounds[0], c});
}
}
if(rev) {
swap(bounds[0], bounds[1]), swap(bounds[2], bounds[3]);
for(auto &i : rects)
swap(i[0], i[1]), swap(i[2], i[3]), rev = 1;
}
if(ans.size() <= k)
return ans;
}
{int p = 0;
for(auto i : rects) {
if(i[0] <= bounds[0] && bounds[0] <= i[2]) p = max(p, i[1]);
}
array<int, 2> P = {bounds[0], p};
auto t = solve(cut(rects, P), k-1);
if(!t.empty() && t.size() < k) {
t.push_back(P);
return t;
}
}
{int p = n+2;
for(auto i : rects) {
if(i[0] <= bounds[0] && bounds[0] <= i[2]) p = min(p, i[3]);
}
array<int, 2> P = {bounds[0], p};
auto t = solve(cut(rects, P), k-1);
if(!t.empty() && t.size() < k) {
t.push_back(P);
return t;
}
}
for(int i = 0; i < 4; i++) {
array<int, 2> P {bounds[2*(i&1)], bounds[1 + (i&2)]};
auto t = solve(cut(rects, P), k-1);
if(!t.empty() && t.size() < k) {
t.push_back(P);
return t;
}
}
return {};
//while(true);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
vector<array<int, 4>> rects(n);
for(auto &i : rects)
for(int j = 0; j < 4; j++) {
cin >> i[j];
cd[j&1].push_back(i[j]);
}
for(int i : {0, 1}) sort(all(cd[i]));
for(auto &i : rects)
for(int j = 0; j < 4; j++) {
i[j] = lower_bound(all(cd[j&1]), i[j]) - cd[j&1].begin();
}
auto ans = solve(rects, k);
while(ans.size() < k) ans.push_back({1, 1});
for(auto [x, y] : ans) cout << cd[0][x] << " " << cd[1][y] << '\n';
/*cout << " ------------- \n";
for(auto [x, y] : ans) cout << x << " " << y << '\n';
for(auto i : ans) rects = cut(rects, i);
for(auto i : rects) cout << i[0] << " " << i[1] << " " << i[2] << " " << i[3] << '\n';
assert(rects.empty());*/
return 0;
}
