#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
Point operator-(const Point p) const { return {x - p.x, y - p.y}; }
void operator+=(const Point p) {
x += p.x;
y += p.y;
}
bool operator<(const Point p) const { return x < p.x || (x == p.x && y < p.y); }
int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
Point dest;
while (cin >> dest.x >> dest.y >> n) {
vector<tuple<int, int, int, int>> events;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);
}
// TODO: This is weird. Make the ordering more explicit as to why it works that way.
const int DEST = -1;
events.emplace_back(dest.x, DEST, dest.y, dest.y);
sort(events.begin(), events.end());
map<int, Point> m;
map<Point, Point> prev_point;
// TODO: Find a better infinity value. Or try to get rid of it.
const int inf = 1e8;
m[0] = {0, 0};
// TODO: This data is weird lmao
m[-inf] = {-inf, -inf};
m[inf] = {-inf, inf};
// TODO: Maybe I can index distances by Y only.
map<Point, int> dist;
dist[{0, 0}] = 0;
const auto update = [&](const Point p) {
const auto it0 = m.lower_bound(p.y);
const auto it1 = it0->first == p.y ? it0 : prev(it0);
for (const auto it : {it0, it1}) {
const Point point = it->second;
// TODO: This looks like a Dijkstra implementation, but it's not, so make it
// adhoc (on purpose).
const int alt = dist[point] + p.dist(point);
if (!dist.count(p) || dist[p] > alt) {
prev_point[p] = point;
dist[p] = alt;
}
}
m[p.y] = p;
};
for (const auto& [x, type, y1, y2] : events) {
// TODO: This is kinda shit.
if (type == DEST) {
update({x, y1});
break;
} else {
update({x, y1});
update({x, y2});
}
while (true) {
const auto it = m.lower_bound(y1 + 1);
if (y2 <= it->first) break;
m.erase(it);
}
}
vector<Point> path;
Point curr = dest;
while (curr.x != 0 || curr.y != 0) {
path.emplace_back(curr);
curr = prev_point[curr];
}
path.emplace_back(curr);
reverse(path.begin(), path.end());
vector<Point> deltas;
const auto add_delta = [&](const Point d) {
if (!deltas.empty() &&
((deltas.back().x == 0 && d.x == 0) || (deltas.back().y == 0 && d.y == 0))) {
deltas.back() += d;
} else {
deltas.emplace_back(d);
}
};
for (size_t i = 0; i + 1 < path.size(); i++) {
const Point d = path[i + 1] - path[i];
if (d.x != 0 && d.y != 0) {
add_delta({d.x, 0});
add_delta({0, d.y});
} else {
add_delta(d);
}
}
int total_len = 0;
for (const Point d : deltas) {
total_len += d.x;
total_len += abs(d.y);
}
cout << total_len << endl;
cout << deltas.size() << endl;
for (const Point d : deltas) {
cout << d.x << ' ' << d.y << endl;
}
}
}
