#include <bits/stdc++.h>
using namespace std;
// TODO: There are a few TODOs to understand some aspects of the logic better.
// TODO: Add to sweep line category.
// TODO: Is this DP? add to DP category???
struct Point {
int x, y;
Point operator-(const Point p) const { return {x - p.x, y - p.y}; }
bool operator==(const Point p) const { return x == p.x && y == p.y; }
int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
struct Hash {
size_t operator()(const Point p) const noexcept {
return (static_cast<size_t>(p.x) << 32) ^ static_cast<size_t>(p.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;
assert(x1 <= x2 && y1 <= y2);
if (dest.x < x1) continue;
events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);
}
sort(events.begin(), events.end());
map<int, int> active;
unordered_map<Point, Point, Point::Hash> parent;
unordered_map<Point, int, Point::Hash> dist;
active[0] = 0;
active[INT_MIN] = 0;
active[INT_MAX] = 0;
dist[{0, 0}] = 0;
const auto update = [&](const Point p) {
const auto it0 = active.lower_bound(p.y);
const auto it1 = prev(it0);
for (const auto it : {it0, it1}) {
const Point prev{it->second, it->first};
if (!dist.count(prev)) continue;
const int new_dist = dist[prev] + p.dist(prev);
if (!dist.count(p) || dist[p] > new_dist) {
dist[p] = new_dist;
parent[p] = prev;
}
// TODO: This line is suspicious. Without it, it gets WA
// Maybe it's because of the ordering of events and some premises
// about the ordering and how points are processed??
if (it0->first == p.y) break;
}
active[p.y] = p.x;
};
for (const auto& [x, _, y1, y2] : events) {
update({x, y1});
update({x, y2});
while (true) {
const auto it = active.lower_bound(y1 + 1);
if (y2 <= it->first) break;
active.erase(it);
}
}
update(dest);
vector<Point> path;
Point curr = dest;
while (curr.x != 0 || curr.y != 0) {
path.emplace_back(curr);
curr = parent[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().x += d.x;
deltas.back().y += d.y;
} 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;
#ifndef DEV
cout << deltas.size() << endl;
for (const Point d : deltas) {
cout << d.x << ' ' << d.y << endl;
}
#endif
}
}
