#include <bits/stdc++.h>
using namespace std;
// ---------------- Structures ------------------
struct Building {
int r; // right coordinate = max(x1,x2)
int lower; // min(y1,y2)
int upper; // max(y1,y2)
int id; // building id
};
// Candidate point (a “corner”)
struct Candidate {
int x, y; // coordinates
int type; // 0: TU (upper candidate), 1: TD (lower candidate)
int bID; // building id (for TU/TD); for dummy candidate (destination) we set bID = -1.
int nxt; // the building id (T) encountered when “looking left” from this candidate; -1 if none.
long long dp; // DP value: minimum distance from S=(0,0) to this candidate along a special path.
int parent; // predecessor candidate index in the DP chain.
};
// Sweep–line event
// For buildings: type 0 = activation (at y = lower), type 1 = deactivation (at y = upper).
// For candidate queries: type 2 = query for TD candidate (at candidate.y), type 3 = query for TU candidate (at candidate.y).
struct Event {
int y;
int type; // 0: activate, 1: deactivate, 2: query TD, 3: query TU
int x; // x coordinate of the event (for building events: building r)
int bID; // building id for activate/deactivate; -1 otherwise.
int candIdx; // candidate index (for query events)
};
// ---------------- Segment Tree ------------------
struct SegNode {
int val; // store the x coordinate (r value) of the building currently active at that index.
int bID; // building id.
};
struct SegmentTree {
int size;
vector<SegNode> tree;
SegmentTree(int n) {
size = 1;
while(size < n) size *= 2;
tree.assign(2 * size, {-1, -1});
}
void update(int pos, int val, int bID) {
pos += size;
tree[pos] = {val, bID};
for(pos /= 2; pos >= 1; pos /= 2) {
if(tree[2*pos].val >= tree[2*pos+1].val)
tree[pos] = tree[2*pos];
else
tree[pos] = tree[2*pos+1];
}
}
SegNode query(int l, int r) {
SegNode res = {-1, -1};
l += size; r += size;
while(l <= r) {
if(l % 2 == 1) {
if(tree[l].val > res.val) res = tree[l];
l++;
}
if(r % 2 == 0) {
if(tree[r].val > res.val) res = tree[r];
r--;
}
l /= 2; r /= 2;
}
return res;
}
};
// ---------------- Helper ------------------
inline long long manhattan(int x1, int y1, int x2, int y2) {
return (long long) abs(x1 - x2) + abs(y1 - y2);
}
// ---------------- Main ------------------
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int X, Y, N;
cin >> X >> Y >> N;
vector<Building> buildings;
buildings.reserve(N);
for (int i = 0; i < N; i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int r = max(x1, x2);
int lower = min(y1, y2);
int upper = max(y1, y2);
buildings.push_back({r, lower, upper, i});
}
// ---------------- Build Candidate Points ------------------
// For each building T, create:
// TU: (T.r, T.upper+1) and TD: (T.r, T.lower-1)
// Also add dummy candidate for destination D = (X,Y).
vector<Candidate> cand;
cand.reserve(2 * N + 1);
// To quickly find a building’s candidates:
vector<int> candTU(N, -1), candTD(N, -1);
for (int i = 0; i < N; i++){
Candidate c;
c.x = buildings[i].r;
c.y = buildings[i].upper + 1;
c.type = 0; // TU
c.bID = buildings[i].id;
c.nxt = -1;
c.dp = 0;
c.parent = -1;
cand.push_back(c);
candTU[buildings[i].id] = cand.size() - 1;
c.x = buildings[i].r;
c.y = buildings[i].lower - 1;
c.type = 1; // TD
c.bID = buildings[i].id;
c.nxt = -1;
c.dp = 0;
c.parent = -1;
cand.push_back(c);
candTD[buildings[i].id] = cand.size() - 1;
}
// Dummy candidate for destination.
Candidate dummy;
dummy.x = X; dummy.y = Y;
// Treat dummy as a TU candidate.
dummy.type = 0;
dummy.bID = -1;
dummy.nxt = -1;
dummy.dp = 0;
dummy.parent = -1;
cand.push_back(dummy);
int dummyIdx = cand.size() - 1;
// ---------------- Build Sweep–line Events ------------------
vector<Event> events;
events.reserve(2 * N + cand.size());
for (int i = 0; i < N; i++){
Event ev;
ev.y = buildings[i].lower;
ev.type = 0; // activation
ev.x = buildings[i].r;
ev.bID = buildings[i].id;
ev.candIdx = -1;
events.push_back(ev);
ev.y = buildings[i].upper;
ev.type = 1; // deactivation
ev.x = buildings[i].r;
ev.bID = buildings[i].id;
ev.candIdx = -1;
events.push_back(ev);
}
// For candidate queries:
// For TU (type==0) candidates: query at y = candidate.y with event type 3.
// For TD (type==1) candidates: query at y = candidate.y with event type 2.
for (int i = 0; i < (int)cand.size(); i++){
Event ev;
ev.y = cand[i].y;
if(cand[i].type == 0) { // TU (or dummy)
ev.type = 3; // query TU
} else { // TD
ev.type = 2; // query TD
}
ev.x = cand[i].x;
ev.candIdx = i;
ev.bID = -1;
events.push_back(ev);
}
// Sort events by y; if equal, by type (activation < query < deactivation)
sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
if(a.y == b.y) return a.type < b.type;
return a.y < b.y;
});
// ---------------- Process Events with Segment Tree ------------------
const int MAXX = 1000002;
SegmentTree seg(MAXX);
for(auto &ev : events){
if(ev.type == 0) { // activation
seg.update(ev.x, ev.x, ev.bID);
} else if(ev.type == 1) { // deactivation
seg.update(ev.x, -1, -1);
} else if(ev.type == 2 || ev.type == 3) { // query events
SegNode res = seg.query(0, ev.x);
cand[ev.candIdx].nxt = res.bID; // -1 if none found
}
}
// ---------------- DP: Process Candidates in increasing order of x (and type order)
// Order: sort by (x ascending, then type where TU (0) comes before TD (1))
vector<int> order(cand.size());
for (int i = 0; i < (int)cand.size(); i++)
order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) {
if(cand[a].x == cand[b].x)
return cand[a].type < cand[b].type;
return cand[a].x < cand[b].x;
});
const long long INF = 1LL << 60;
vector<long long> dp(cand.size(), INF);
vector<int> par(cand.size(), -1);
// Base: For any candidate with no blocking building (nxt == -1), dp = x + |y|
for (int idx : order) {
if(cand[idx].nxt == -1) {
dp[idx] = cand[idx].x + (long long) abs(cand[idx].y);
par[idx] = -1;
} else {
int r = cand[idx].nxt; // building id that blocks candidate idx
int idxTU = candTU[r];
int idxTD = candTD[r];
long long opt1 = dp[idxTU] + manhattan(cand[idx].x, cand[idx].y, cand[idxTU].x, cand[idxTU].y);
long long opt2 = dp[idxTD] + manhattan(cand[idx].x, cand[idx].y, cand[idxTD].x, cand[idxTD].y);
if(opt1 <= opt2) {
dp[idx] = opt1;
par[idx] = idxTU;
} else {
dp[idx] = opt2;
par[idx] = idxTD;
}
}
// If two candidates come from the same building (i.e. same x and same bID, and bID != -1),
// update both to the same (minimum) dp value.
if(cand[idx].bID != -1) {
// Look ahead in order for another candidate from the same building
// (since buildings produce exactly two candidates).
// (They have the same x; our sort order ensures TU comes before TD.)
// We can update both.
// Find next candidate with same x and same building id.
int j = idx + 1;
if(j < (int)order.size()){
int idx2 = order[j];
if(cand[idx2].bID == cand[idx].bID && cand[idx2].x == cand[idx].x) {
long long bestVal = min(dp[idx], dp[idx2]);
dp[idx] = dp[idx2] = bestVal;
}
}
}
}
// Save DP and parent info back to candidates.
for (int i = 0; i < (int)cand.size(); i++){
cand[i].dp = dp[i];
cand[i].parent = par[i];
}
// The answer is the dp for the dummy candidate.
long long ans = cand[dummyIdx].dp;
// ---------------- Reconstruct the Candidate Chain ------------------
vector<int> chain;
int cur = dummyIdx;
while(cur != -1) {
chain.push_back(cur);
cur = cand[cur].parent;
}
reverse(chain.begin(), chain.end());
// Now chain[0] will be the candidate reached directly from S.
// (S itself is not among the candidates.)
// ---------------- Reconstruct the Path Polyline ------------------
// We now “simulate” the special path using a safe routing rule:
// • From S = (0,0) to the first candidate P:
// – Since S is not attached to a building, we “exit” safely by moving vertically first,
// then horizontally.
// • From a candidate (which is on a building’s boundary) to the next candidate,
// the only safe move is to continue horizontally (to stay on the building boundary)
// and then change vertically.
vector<pair<int,int>> polyline;
// Start at S = (0,0)
polyline.push_back({0,0});
// If there is at least one candidate in the chain, define P0 = chain[0]'s coordinates.
// For leg 0 (from S to chain[0]): use vertical-then-horizontal.
if(!chain.empty()){
int idx = chain[0];
int targetX = cand[idx].x;
int targetY = cand[idx].y;
// Vertical move from (0,0) to (0, targetY)
polyline.push_back({0, targetY});
// Horizontal move from (0, targetY) to (targetX, targetY)
polyline.push_back({targetX, targetY});
}
// For subsequent legs (from candidate i to candidate i+1), use horizontal-first.
for (size_t i = 0; i + 1 < chain.size(); i++){
int currIdx = chain[i];
int nextIdx = chain[i+1];
int currX = cand[currIdx].x, currY = cand[currIdx].y;
int nextX = cand[nextIdx].x, nextY = cand[nextIdx].y;
// From current candidate, move horizontally to nextX while staying at currY.
polyline.push_back({nextX, currY});
// Then move vertically from (nextX, currY) to (nextX, nextY).
polyline.push_back({nextX, nextY});
}
// ---------------- Compress Polyline Segments ------------------
// Merge consecutive segments in the same direction.
vector<pair<int,int>> segments;
// First compute segments from polyline points.
vector<pair<int,int>> pts = polyline;
// Remove consecutive duplicate points.
vector<pair<int,int>> clean;
clean.push_back(pts[0]);
for (size_t i = 1; i < pts.size(); i++){
if(pts[i] != clean.back())
clean.push_back(pts[i]);
}
for (size_t i = 0; i + 1 < clean.size(); i++){
int dx = clean[i+1].first - clean[i].first;
int dy = clean[i+1].second - clean[i].second;
segments.push_back({dx, dy});
}
// Further compress if two consecutive segments are in the same direction.
vector<pair<int,int>> comp;
if(!segments.empty()){
comp.push_back(segments[0]);
for (size_t i = 1; i < segments.size(); i++){
auto &last = comp.back();
// Same direction if both dx are zero or both dy are zero.
if((last.first == 0 && segments[i].first == 0) ||
(last.second == 0 && segments[i].second == 0)){
last.first += segments[i].first;
last.second += segments[i].second;
} else {
comp.push_back(segments[i]);
}
}
}
// ---------------- Output ------------------
cout << ans << "\n";
cout << comp.size() << "\n";
for (auto &seg : comp)
cout << seg.first << " " << seg.second << "\n";
return 0;
}
