#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100100
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
#define left __left
#define right __right
template<class X,class Y> bool maximize(X &x,Y y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class X,class Y> bool minimize(X &x,Y y)
{
if(y<x)
{
x=y;
return 1;
}
return 0;
}
const int inf=1e9+412009;
const ll INF=2e18+412009;
struct POINT
{
int x,y;
int id;
void input(int i=0)
{
cin>>x>>y;
id=i;
}
bool operator < (POINT other) const
{
return x==other.x ? y<other.y : x<other.x;
}
};
double LEN(POINT a,POINT b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
struct RECT
{
int top,bot,left,right;
int id;
void input(int i=0)
{
id=i;
int x,y,u,v;
cin>>x>>y>>u>>v;
top=max(y,v);
bot=min(y,v);
right=max(x,u);
left=min(x,u);
}
};
POINT S={0,0,0},T;
int n;
RECT a[MAX];
void nhap()
{
T.input(1);
cin>>n;
for(int i=1;i<=n;i++) a[i].input(i);
}
vector<POINT> events;
vector<POINT> vertex;
set<POINT> s;
map<pii,int> usedpoint;
map<pii,bool> banpoint;
vector<int> adj[10*MAX];
void connect(int u,int v)
{
if(u==-1||v==-1) return;
if(vertex[v]<vertex[u]) swap(u,v);
if(vertex[u].x==vertex[v].x||vertex[u].y==vertex[v].y)
{
adj[u].push_back(v);
adj[v].push_back(u);
return;
}
POINT middle={vertex[v].x,vertex[u].y,(int)vertex.size()};
if(usedpoint[{middle.x,middle.y}])
{
middle.id=usedpoint[{middle.x,middle.y}];
}
else vertex.push_back(middle),usedpoint[{middle.x,middle.y}]=middle.id;
adj[u].push_back(middle.id);adj[middle.id].push_back(u);
adj[v].push_back(middle.id);adj[middle.id].push_back(v);
}
void newvertex(pii a,int newid=vertex.size())
{
if(banpoint.find(a)!=banpoint.end()) return;
if(usedpoint.find(a)!=usedpoint.end()||a.fi==0&&a.se==0) newid=usedpoint[a];
auto it1=s.lower_bound({a.se,-inf,-inf});
auto it2=it1;
int up=-1,down=-1;
if(it1!=s.end())
{
if(it1->y==-inf&&it1->x==a.se) return;
if(it1->y!=-inf) up=it1->id;
}
if(it1!=s.begin())
{
it2--;
if(it2->y==-inf&&it2->x==a.se) return;
if(it2->y!=-inf) down=it2->id;
}
if(newid==(int)vertex.size()) vertex.push_back({a.fi,a.se,newid});
usedpoint[a]=newid;
connect(up,newid);
connect(down,newid);
s.insert({a.se,a.fi,newid});
}
void load_Graph()
{
usedpoint[{S.x,S.y}]=0;
usedpoint[{T.x,T.y}]=1;
for(int i=1;i<=n;i++)
{
int top=a[i].top;
int bot=a[i].bot;
int left=a[i].left;
int right=a[i].right;
banpoint[{left,top}]=1;
banpoint[{right,top}]=1;
banpoint[{left,bot}]=1;
banpoint[{right,bot}]=1;
events.push_back({left,-inf,i});
events.push_back({right,-inf+1,i});
}
events.push_back({S.x,S.y,0});
events.push_back({T.x,T.y,1});
sort(all(events));
for(POINT p:events)
{
int id=p.id;
if(p.y<=-inf+1)
{
if(p.y==-inf)
{
newvertex({a[id].left-1,a[id].top+1});
newvertex({a[id].left-1,a[id].bot-1});
vector<POINT> eraseit;
for(auto it=s.lower_bound({a[id].bot,-inf,-inf});it!=s.end()&&it->x<=a[id].top;it++) eraseit.push_back(*it);
for(POINT j:eraseit) s.erase(j);
s.insert({a[id].bot,-inf,id});
s.insert({a[id].top,-inf,id});
}
else
{
newvertex({a[id].right+1,a[id].top+1});
newvertex({a[id].right+1,a[id].bot-1});
s.erase({a[id].bot,-inf,id});
s.erase({a[id].top,-inf,id});
}
}
else newvertex({p.x,p.y},id);
}
}
ll dist[10*MAX];
ll trace[10*MAX]={};
void solve()
{
vertex.push_back(S);
vertex.push_back(T);
load_Graph();
memset(dist,0x3f,sizeof(dist));
priority_queue<pll,vector<pll>,greater<pll>> pq;
dist[0]=0;
pq.push({0,0});
while(!pq.empty())
{
pll tmp=pq.top();pq.pop();
ll kc=tmp.fi;
int u=tmp.se;
if(kc!=dist[u]) continue;
for(int v:adj[u]) if(minimize(dist[v],dist[u]+LEN(vertex[u],vertex[v])))
{
pq.push({dist[v],v});
trace[v]=u;
}
}
cout<<dist[1]<<'\n';
// for(int i=0;i<vertex.size();i++)
// {
// cout<<vertex[i].x<<' '<<vertex[i].y<<' '<<vertex[i].id<<' '<<trace[i]<<'\n';
// }
vector<pii> tracing;
int u=1;
while(u!=0)
{
int v=trace[u];
POINT pu=vertex[u],pv=vertex[v];
//cout<<pu.x<<' '<<pu.y<<'\n';
if(pu.y==pv.y)
{
pii tmp={pu.x-pv.x,0};
if(!tracing.empty()&&tracing.back().se==0) tracing.back().fi+=tmp.fi;
else tracing.push_back(tmp);
}
else
{
pii tmp={0,pu.y-pv.y};
if(!tracing.empty()&&tracing.back().fi==0) tracing.back().se+=tmp.se;
else tracing.push_back(tmp);
}
u=v;
}
reverse(all(tracing));
cout<<tracing.size()<<'\n';
for(pii p:tracing) cout<<p.fi<<' '<<p.se<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
nhap();
solve();
return 0;
}
