#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii; // (x, y, dir)
const int INF = 1e9;
const int dx[4] = {1, -1, 0, 0}; // right, left, up, down
const int dy[4] = {0, 0, 1, -1};
const int dir_type[4] = {1, 1, 2, 2}; // 1=horizontal, 2=vertical
int main() {
int X, Y, N;
cin >> X >> Y >> N;
// Mark blocked squares
set<pii> blocked;
for (int i = 0; i < N; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int xmin = min(x1, x2), xmax = max(x1, x2);
int ymin = min(y1, y2), ymax = max(y1, y2);
for (int x = xmin; x <= xmax; x++)
for (int y = ymin; y <= ymax; y++)
blocked.insert({x, y});
}
// BFS
vector<vector<vector<int>>> dist(2001, vector<vector<int>>(2001, vector<int>(3, INF))); // Adjust size as needed
vector<vector<vector<tiii>>> parent(2001, vector<vector<tiii>>(2001, vector<tiii>(3)));
queue<tiii> q;
dist[0][0][0] = 0;
q.push({0, 0, 0});
while (!q.empty()) {
auto [x, y, dir] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
int new_dir = dir_type[d];
// Skip if out of bounds, blocked, or same direction as previous
if (nx < -1000 || nx > 2000 || ny < -1000 || ny > 2000 || blocked.count({nx, ny})) continue;
if (dir != 0 && dir == new_dir) continue;
if (dist[nx][ny][new_dir] == INF) {
dist[nx][ny][new_dir] = dist[x][y][dir] + 1;
parent[nx][ny][new_dir] = {x, y, dir};
q.push({nx, ny, new_dir});
}
}
}
// Find shortest path to (X, Y)
int L = INF, final_dir = -1;
for (int d = 1; d <= 2; d++) {
if (dist[X][Y][d] < L) {
L = dist[X][Y][d];
final_dir = d;
}
}
if (L == INF) {
cout << "No path found\n"; // Shouldn’t happen given problem constraints
return 0;
}
// Reconstruct path
vector<pair<int, int>> segments;
int cx = X, cy = Y, cd = final_dir;
while (!(cx == 0 && cy == 0 && cd == 0)) {
auto [px, py, pd] = parent[cx][cy][cd];
int dx = cx - px, dy = cy - py;
segments.push_back({dx, dy});
cx = px; cy = py; cd = pd;
}
// Merge consecutive moves into segments
vector<pair<int, int>> final_segments;
int curr_dx = 0, curr_dy = 0;
for (int i = segments.size() - 1; i >= 0; i--) {
int dx = segments[i].first, dy = segments[i].second;
if (dx != 0) {
if (curr_dy != 0) {
final_segments.push_back({0, curr_dy});
curr_dy = 0;
}
curr_dx += dx;
} else {
if (curr_dx != 0) {
final_segments.push_back({curr_dx, 0});
curr_dx = 0;
}
curr_dy += dy;
}
}
if (curr_dx != 0) final_segments.push_back({curr_dx, 0});
if (curr_dy != 0) final_segments.push_back({0, curr_dy});
// Output
cout << L << "\n";
cout << final_segments.size() << "\n";
for (auto [dx, dy] : final_segments) {
cout << dx << " " << dy << "\n";
}
return 0;
}
