#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int inf = 1<<30;
struct Rect {
array<array<int, 2>, 2> ranges;
void rotate(int c) {
while(c--) {
for(int i = 0; i < 2; i++) {
ranges[0][i] = -exchange(ranges[1][i], ranges[0][i]);
}
for(int i = 0; i < 2; i++) {
if(ranges[i][0] > ranges[i][1])
swap(ranges[i][0], ranges[i][1]);
}
}
}
friend Rect intersect(const Rect &a, const Rect &b) {
Rect res;
for(int i = 0; i < 2; i++) {
res.ranges[i][0] = max(a.ranges[i][0], b.ranges[i][0]);
res.ranges[i][1] = min(a.ranges[i][1], b.ranges[i][1]);
}
return res;
}
bool contains(array<int, 2> P) {
for(int i = 0; i < 2; i++) {
if(P[i] < ranges[i][0] || P[i] > ranges[i][1])
return false;
}
return true;
}
bool empty() {
for(int i = 0; i < 2; i++)
if(ranges[i][0] > ranges[i][1])
return true;
return false;
}
};
Rect intersectAll(vector<Rect> &v) {
Rect res;
res.ranges[0][0] = res.ranges[1][0] = -inf;
res.ranges[0][1] = res.ranges[1][1] = inf;
for(auto &i : v)
res = intersect(res, i);
return res;
}
vector<Rect> prune(vector<Rect> v, array<int, 2> P) {
vector<Rect> res;
for(auto i : v) if(!i.contains(P)) {
res.push_back(i);
}
return res;
}
array<vector<int>, 2> compress(vector<Rect> &v) {
array<vector<int>, 2> clist;
for(auto r : v) {
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
clist[i].push_back(r.ranges[i][j]);
}
}
}
for(auto &c : clist) sort(all(c)), c.erase(unique(all(c)), c.end());
for(auto &r : v) {
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
r.ranges[i][j] = lower_bound(all(clist[i]), r.ranges[i][j]) - clist[i].begin();
}
}
}
return clist;
}
// Solve k<=3 and k=4 if we use a corner or intersection is non-empty
vector<array<int, 2>> solve_corner(vector<Rect> rects, int k) {
if(k < 1) return {};
//All intersect use 1, not tested
Rect I = intersectAll(rects);
if(I.ranges[0][0] <= I.ranges[0][1] && I.ranges[1][0] <= I.ranges[1][1]) {
return {{I.ranges[0][0], I.ranges[1][0]}};
}
// for(auto &c : I.ranges) {
// for(auto &v : c) cout << v << ", ";
// cout << endl;
// }
//1D case; not tested
int rot = 0;
if(I.ranges[1][0] <= I.ranges[1][1]) {
rot++;
I.rotate(1);
for(auto &i : rects) i.rotate(1);
}
if(I.ranges[0][0] <= I.ranges[0][1]) {
vector<array<int, 2>> segs;//{R, L}
for(auto r : rects) {
segs.push_back({r.ranges[1][1], r.ranges[1][0]});
}
sort(all(segs));
int covered = -1;
vector<array<int, 2>> sol;
for(auto [r, l] : segs) {
if(l <= covered) {
assert(covered <= r);
} else {
sol.push_back({I.ranges[0][0], covered = r});
}
}
if(sol.size() > k) return {};
if(rot) {
for(auto &[x, y] : sol) {
y = -exchange(x, y);
}
}
return sol;
}
assert(!rot);
//Use corner case; not tested
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
array<int, 2> P = {I.ranges[0][i], I.ranges[1][j]};
auto tmp = solve_corner(prune(rects, P), k - 1);
if(!tmp.empty()) {
tmp.push_back(P);
return tmp;
}
}
}
return {};
}
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct TwoSat {
int N;
vector<vi> gr;
vi values; // 0 = false, 1 = true
TwoSat(int n = 0) : N(n), gr(2*n) {}
int addVar() { // (optional)
gr.emplace_back();
gr.emplace_back();
return N++;
}
void either(int f, int j) {
f = max(2*f, -1-2*f);
j = max(2*j, -1-2*j);
gr[f].push_back(j^1);
gr[j].push_back(f^1);
}
void setValue(int x) { either(x, x); }
void atMostOne(const vi& li) { // (optional)
if (sz(li) <= 1) return;
int cur = ~li[0];
rep(i,2,sz(li)) {
int next = addVar();
either(cur, ~li[i]);
either(cur, next);
either(~li[i], next);
cur = ~next;
}
either(cur, ~li[1]);
}
vi val, comp, z; int time = 0;
int dfs(int i) {
int low = val[i] = ++time, x; z.push_back(i);
for(int e : gr[i]) if (!comp[e])
low = min(low, val[e] ?: dfs(e));
if (low == val[i]) do {
x = z.back(); z.pop_back();
comp[x] = low;
if (values[x>>1] == -1)
values[x>>1] = x&1;
} while (x != i);
return val[i] = low;
}
bool solve() {
values.assign(N, -1);
val.assign(2*N, 0); comp = val;
rep(i,0,2*N) if (!comp[i]) dfs(i);
rep(i,0,N) if (comp[2*i] == comp[2*i+1]) return 0;
return 1;
}
};
//solve k=4, no point in the corner -> all on the perimeter
vector<array<int, 2>> solve_perim(vector<Rect> rects) {
auto clist = compress(rects);
Rect I = intersectAll(rects);
swap(I.ranges[0][0], I.ranges[0][1]);
swap(I.ranges[1][0], I.ranges[1][1]);
for(int i = 0; i < 2; i++) assert(I.ranges[i][0] < I.ranges[i][1]);//because we already used the other function
// cout << I.ranges[0][0] << " " << I.ranges[0][1] << endl;
// cout << I.ranges[1][0] << " " << I.ranges[1][1] << endl;
vector<vector<int>> myVars(rects.size());
vector<int> starts;
TwoSat sat;
for(int c = 0; c < 2; c++) {
for(int x = 0; x < 2; x++) {
Rect l = I;
l.ranges[c][x] = l.ranges[c][x^1];
l.ranges[c^1][0]++;
l.ranges[c^1][1]--;
int len = l.ranges[c^1][1] - l.ranges[c^1][0] + 1;
// cout << l.ranges[c][x] << " : " << l.ranges[c^1][0] << " " << l.ranges[c^1][1] << endl;
int start = sat.addVar();
starts.push_back(start);
sat.setValue(~start);
for(int i = 1; i <= len; i++) {
assert(sat.addVar() == start + i);
sat.either(~(start + i - 1), (start + i));
}
int lid = 2*c+x;
for(int i = 0; i < rects.size(); i++) {
auto inter = intersect(l, rects[i]);
// cout << "I" << inter.ranges[c][x] << " : " << inter.ranges[c^1][0] << " " << inter.ranges[c^1][1] << endl;
if(inter.empty()) continue;
int b = inter.ranges[c^1][0] - l.ranges[c^1][0] + 1;
int e = inter.ranges[c^1][1] - l.ranges[c^1][0] + 1;
int x = sat.addVar();
myVars[i].push_back(x);
sat.either(~x, ~(start + b - 1));
sat.either(~x, start + e);
// cout << "Line " << lid << "; Rect " << i << "_" << x << " : not " << start + b - 1 << " or " << start + e << endl;
}
}
}
for(auto v : myVars) {
if(v.size() == 1) sat.setValue(v[0]);//, cout << "SET " << v[0] << endl;
if(v.size() == 2) sat.either(v[0], v[1]);//, cout << "OR " << v[0] << " " << v[1] << endl;
}
assert(sat.solve());
vector<array<int, 2>> ans;
for(int c = 0; c < 2; c++) {
for(int x = 0; x < 2; x++) {
Rect l = I;
l.ranges[c][x] = l.ranges[c][x^1];
l.ranges[c^1][0]++;
l.ranges[c^1][1]--;
int len = l.ranges[c^1][1] - l.ranges[c^1][0] + 1;
int start = starts[c*2+x];
// for(int i = 0; i <= len; i++) {
// cout << sat.values[start+i] << " ";
// }cout << endl;
array<int, 2> pt;
pt[c] = l.ranges[c][x];
pt[c^1] = l.ranges[c^1][0] - 1;
while(!sat.values[start]) {
start++;
pt[c^1]++;
}
ans.push_back(pt);
}
}
for(auto &i : ans) {
for(int c = 0; c < 2; c++) {
i[c] = clist[c][i[c]];
}
}
return ans;
}
vector<array<int, 2>> solve() {
int n, k;
cin >> n >> k;
vector<Rect> rects(n);
for(auto &r : rects) {
// cin >> r.ranges[0][0] >> r[1][0] >> r[0][1] >> r[1][1];
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
cin >> r.ranges[j][i];
}
auto res = solve_corner(rects, k);
if(res.empty() && k == 4) {
res = solve_perim(rects);
}
assert(!res.empty());
while(res.size() < k) res.push_back(res.back());
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
auto out = solve();
for(auto [x, y] : out) {
cout << x << " " << y << '\n';
}
}
