#include <bits/stdc++.h>
using namespace std;
#define int ll
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;
const int INF = 1e9 + 71;
struct steak {
ii h, v;
bool inside(ii pct) {
return h.first <= pct.first && pct.first <= h.second
&& v.first <= pct.second && pct.second <= v.second;
}
};
ii seg_extremums(vector<ii> V) {
int l = -INF, r = INF;
for(auto [s, d] : V) {
l = max(l, s);
r = min(r, d);
}
return {l, r};
}
tuple<int, int, int, int> get_steak_extremums(vector<steak> S) {
vector<ii> H, V;
for(auto [h, v] : S) {
H.push_back(h); V.push_back(v);
}
auto [lh, rh] = seg_extremums(H);
auto [lv, rv] = seg_extremums(V);
return {lh, rh, lv, rv};
}
vector<ii> sol_k2(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> re;
auto check_sol = [&](ii p1, ii p2) -> bool{
bool ok = true;
for(auto it : S) {
ok &= it.inside(p1) || it.inside(p2);
if(!ok) break;
}
if(ok) {
re = vector<ii>{p1, p2};
}
return ok;
};
check_sol(ii{lh, lv}, ii{rh, rv});
check_sol(ii{lh, rv}, ii{rh, lv});
return re;
}
vector<ii> sol_k1(vector<steak> S) {
auto [lh, rh, lv, rv] = get_steak_extremums(S);
if(lh <= rh && lv <= rv) return vector<ii>{ii{lh, lv}};
return vector<ii>();
}
vector<ii> sol_k3(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> Re;
auto check_rest = [&](ii p) {
vector<steak> LeftOver;
for(auto it : S)
if(!it.inside(p)) LeftOver.push_back(it);
auto Cur = sol_k2(LeftOver);
if(!Cur.empty()) {
Cur.push_back(p);
Re = Cur;
}
};
vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
for(auto it : Corners) check_rest(it);
return Re;
}
vector<pair<int, ii> > get_intersect(steak x, vector<ii> &Corners) {
///returns a vector of (edge id, (min max allowed))
auto get_overlap0 = [&](ii seg, int l, int r) {
if(l > r) swap(l, r);
return ii{max(l, seg.first), min(r, seg.second)};
};
auto get_overlap = [&](ii p1, ii p2) {
if(p1.first == p2.first) return get_overlap0(x.v, p1.second, p2.second);
return get_overlap0(x.h, p1.first, p2.first);
};
vector<pair<int, ii> > Re;
for(int i = 0; i < 4; ++i) {
auto re = get_overlap(Corners[i], Corners[(i + 1) % 4]);
if(re.first <= re.second) Re.push_back({i, re});
}
return Re;
}
ii intersect(ii a, ii b) {
return {max(a.first, b.first), min(a.second, b.second)};
}
struct RestrictionDS {
vector<pair<ii, ii> > V;
void add(ii x1, ii x2) {
///if a in x1 -> b in x2
V.push_back({x1, x2});
}
void init() {
}
ii eval(int p) {
ii re{-INF, INF};
for(auto [x1, x2] : V) {
auto [l1, r1] = x1;
if(l1 <= p && r1 <= p) re = intersect(re, x2);
}
return re;
}
};
vector<ii> sol_k4_special(vector<steak> S) {
auto [lh, rh, lv, rv] = get_steak_extremums(S);
int h = lv - rv, w = lh - rh;
vector<ii> Corners = { {0, 0}, {0, h}, {w, h}, {w, 0}, };
vector<ii> FullSeg = { {0, h}, {0, w}, {0, h}, {0, w} }; /// for negations
auto negate = [&](ii seg, ii full) {
assert(seg.first <= seg.second);
vector<ii> Rez;
if(seg.second < full.second) Rez.push_back({seg.second + 1, full.second});
if(full.first < seg.first) Rez.push_back({full.first + 1, seg.first - 1});
return Rez;
};
for(auto &it : S) {
it.h.first -= rh; it.h.second -= rh;
it.v.first -= rv; it.v.second -= rv;
}
array<RestrictionDS, 4> Basic;
array<array<RestrictionDS, 4>, 4> Forbid;
vi Order = {0, 3, 1, 2}, RankOrd = {0, 2, 3, 1};
for(auto x : S) {
int nrc = 0;
for(auto p : Corners) nrc += x.inside(p);
if(nrc > 1) { /// contains one whole edge; is surely covered
continue;
}
auto Inter = get_intersect(x, Corners);
if(Inter.size() == 1) { ///simple restriction
Basic[Inter[0].first].add(ii{0, 0}, Inter[0].second);
} else {
if(RankOrd[Inter[0].first] < RankOrd[Inter[1].first]) swap(Inter[0], Inter[1]);
auto [id0, seg0] = Inter[0]; auto [id1, seg1] = Inter[1];
for(auto it : negate(seg0, FullSeg[id0])) Forbid[id0][id1].add(it, seg1);
}
}
for(auto &it : Basic) it.init();
for(auto &sir : Forbid)
for(auto &it : sir) it.init();
vi X_posib;
for(auto [h, v] : S) {
X_posib.push_back(h.first); X_posib.push_back(h.second);
}
sort(X_posib.begin(), X_posib.end());
X_posib.resize(unique(X_posib.begin(), X_posib.end()) - X_posib.begin());
vector<ii> RestrictiiInit;
for(auto BS : Basic) RestrictiiInit.push_back(BS.eval(0));
for(auto x0 : X_posib) {
///now choose the others greedly
vector<ii> Rest = RestrictiiInit;
vi X = {x0};
bool ok = true;
for(int i = 1; i < 4; ++i) {
for(int j = i; j < 4; ++j) {
Rest[j] = intersect(Rest[j], Forbid[i - 1][j].eval(X[i - 1]));
}
if(Rest[i].first > Rest[i].second) {
ok = false;
break;
}
X.push_back(Rest[i].second);
}
if(!ok) continue;
for(int i = 0; i < 4; ++i)
ok &= Rest[i].first <= X[i] && X[i] <= Rest[i].second;
if(ok) {
///avem o solutie
vector<ii> Re = {{0, X[0]}, {X[1], h}, {w, X[2]}, {X[3], 0}};
for(auto &[x, y] : Re) {
x += rh; y += rv;
const int LIM = 1e9;
if(abs(x) > LIM) x = x / abs(x) * LIM;
if(abs(y) > LIM) y = y / abs(y) * LIM;
}
return Re;
}
}
assert(0);
}
vector<ii> sol_k4(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> Re;
auto check_rest = [&](ii p) {
vector<steak> LeftOver;
for(auto it : S)
if(!it.inside(p)) LeftOver.push_back(it);
auto Cur = sol_k3(LeftOver);
if(!Cur.empty()) {
Cur.push_back(p);
Re = Cur;
}
};
vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
for(auto p : Corners) check_rest(p);
if(!Re.empty())
return Re;
/// now we're sure no corners are used
Re = sol_k4_special(S);
if(!Re.empty()) return Re;
for(auto &it : S) {
it.v.first *= -1; it.v.second *= -1;
swap(it.v.first, it.v.second);
}
Re = sol_k4_special(S);
assert(!Re.empty());
for(auto &[x, y] : Re) y *= -1;
return Re;
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<steak> S(n);
for(int i = 0; i < n; ++i) {
cin >> S[i].h.first >> S[i].v.first >> S[i].h.second >> S[i].v.second;
}
vector<ii> Re;
if(k == 1) Re = sol_k1(S);
if(k == 2) Re = sol_k2(S);
if(k == 3) Re = sol_k3(S);
if(k == 4) Re = sol_k4(S);
for(auto it : Re) cout << it.first << " " << it.second << "\n";
return 0;
}
