#include<bits/stdc++.h>
using namespace std;
map<int,int>mapx, mapy;
struct rect{int a, b, c, d; int id;};
vector<rect>pros;
bool cmp1(rect a, rect b){
return a.a < b.a;
}
bool cmp2(rect a, rect b){
return a.c < b.c;
}
bool cmp3(rect a, rect b){
return a.b > b.b;
}
bool cmp4(rect a, rect b){
return a.d > b.d;
}
struct oX{int x, p, k, id, dist;};
struct oY{int y, p, k, id, dist;};
oX oXs[400010];
oY oYs[400010];
bool przecina(int x, int y){
if(oXs[x].p<=oYs[y].y && oXs[x].k>=oYs[y].y && oYs[y].p<=oXs[x].x && oYs[y].k>=oXs[x].x)
return 1;
return 0;
}
const int base = 1<<18;
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int val){
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w] = val;
return;
}
if(tree[w]!=-1)
tree[w*2] = tree[w*2+1] = tree[w];
tree[w] = -1;
ustaw(w*2, l, (l+p)/2, a, b, val);
ustaw(w*2+1, (l+p)/2+1, p, a, b, val);
}
int value(int w){
int ans = -1;
w+=base;
while(w>0){
if(tree[w]!=-1)
ans = tree[w];
w/=2;
}
return ans;
}
set<pair<int,int>>treex[2*base], treey[2*base];
void dodajx(int w, int l, int p, int a, int b, int val1, int val2){
if(l>b || p<a)return;
if(a<=l && p<=b){
treex[w].insert({val1, val2});
return;
}
dodajx(w*2, l, (l+p)/2, a, b, val1, val2);
dodajx(w*2+1, (l+p)/2+1, p, a, b, val1, val2);
}
void dodajy(int w, int l, int p, int a, int b, int val1, int val2){
if(l>b || p<a)return;
if(a<=l && p<=b){
treey[w].insert({val1, val2});
return;
}
dodajy(w*2, l, (l+p)/2, a, b, val1, val2);
dodajy(w*2+1, (l+p)/2+1, p, a, b, val1, val2);
}
int main()
{
int sx, sy, tx, ty, n, i;
scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
mapx[sx]=0;
mapx[tx]=0;
mapy[sy]=0;
mapy[ty]=0;
for(i=0;i<n;i++){
pros.push_back({});
scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
mapx[pros.back().a] = mapx[pros.back().b] = 0;
mapy[pros.back().c] = mapy[pros.back().d] = 0;
}
i = 0;
for(auto &ij: mapx)
ij.second = i++;
i = 0;
for(auto &ij: mapy)
ij.second = i++;
sx = mapx[sx];
tx = mapx[tx];
sy = mapy[sy];
ty = mapy[ty];
for(auto &ij: pros){
ij.a = mapx[ij.a];
ij.b = mapx[ij.b];
ij.c = mapy[ij.c];
ij.d = mapy[ij.d];
}
pros.push_back({sx, sx, sy, sy});//start ma id n
pros.push_back({tx, tx, ty, ty});//koniec ma id n+1
for(i=0;i<n+2;i++){
pros[i].id = i;
oXs[i*4+0].x = pros[i].a;
oYs[i*4+1].y = pros[i].c;
oXs[i*4+2].x = pros[i].b;
oYs[i*4+3].y = pros[i].d;
}
sort(pros.begin(), pros.end(), cmp1);
ustaw(1, 0, base-1, 0, 2*(n+1), 0);
for(auto &ij: pros){
oYs[ij.id*4+1].p = value(ij.c);
oYs[ij.id*4+3].p = value(ij.d);
ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.b);
}
sort(pros.begin(), pros.end(), cmp2);
ustaw(1, 0, base-1, 0, 2*(n+1), 0);
for(auto &ij: pros){
oXs[ij.id*4+0].p = value(ij.a);
oXs[ij.id*4+2].p = value(ij.b);
ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.d);
}
sort(pros.begin(), pros.end(), cmp3);
ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
for(auto &ij: pros){
oYs[ij.id*4+1].k = value(ij.c);
oYs[ij.id*4+3].k = value(ij.d);
ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.a);
}
sort(pros.begin(), pros.end(), cmp4);
ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
for(auto &ij: pros){
oXs[ij.id*4+0].k = value(ij.a);
oXs[ij.id*4+2].k = value(ij.b);
ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.c);
}
if(sx==tx){
if(oXs[n*4+0].p<=ty && oXs[n*4+0].k>=ty){
printf("1\n");return 0;
}
}
if(sy==ty){
if(oYs[n*4+1].p<=tx && oYs[n*4+1].k>=tx){
printf("1\n");return 0;
}
}
for(i=0;i<(n+2)*4;i+=2){
if(i!= n*4+0 && i!=n*4+2){
dodajx(1, 0, base-1, oXs[i].p, oXs[i].k, oXs[i].x, i);
}
}
for(i=1;i<(n+2)*4;i+=2){
if(i!= n*4+1 && i!=n*4+3){
dodajy(1, 0, base-1, oYs[i].p, oYs[i].k, oYs[i].y, i);
}
}
queue<int>kolejka;
oXs[n*4+0].dist = 1;
oXs[n*4+2].dist = 1;
oYs[n*4+1].dist = 1;
oYs[n*4+3].dist = 1;
kolejka.push(n*4+0);
kolejka.push(n*4+1);
kolejka.push(n*4+2);
kolejka.push(n*4+3);
while(kolejka.size()){
auto ij = kolejka.front();
kolejka.pop();
if(ij%2==0){
auto A = oXs[ij];
int pom = A.x+base;
while(pom>0){
while(treey[pom].lower_bound({A.p, 0})!=treey[pom].end() && (*treey[pom].lower_bound({A.p, 0})).first<=A.k){
auto pom2 = *treey[pom].lower_bound({A.p, 0});
treey[pom].erase(pom2);
if(oYs[pom2.second].dist==0){
oYs[pom2.second].dist = A.dist+1;
kolejka.push(pom2.second);
}
}
pom/=2;
}
}
else{
auto A = oYs[ij];
int pom = A.y+base;
while(pom>0){
while(treex[pom].lower_bound({A.p, 0})!=treex[pom].end() && (*treex[pom].lower_bound({A.p, 0})).first<=A.k){
auto pom2 = *treex[pom].lower_bound({A.p, 0});
treex[pom].erase(pom2);
if(oXs[pom2.second].dist==0){
oXs[pom2.second].dist = A.dist+1;
kolejka.push(pom2.second);
}
}
pom/=2;
}
}
}
printf("%d\n", min({oXs[(n+1)*4+0].dist, oXs[(n+1)*4+2].dist, oYs[(n+1)*4+1].dist, oYs[(n+1)*4+3].dist}));
/*
printf("X:\n");
for(i=0;i<=(n+1);i++){
printf("%d %d %d %d %d\n", oXs[i*4+0].x, oXs[i*4+0].p, oXs[i*4+0].k, oXs[i*4+0].id, oXs[i*4+0].dist);
printf("%d %d %d %d %d\n", oXs[i*4+2].x, oXs[i*4+2].p, oXs[i*4+2].k, oXs[i*4+2].id, oXs[i*4+2].dist);
}
printf("Y:\n");
for(i=0;i<=(n+1);i++){
printf("%d %d %d %d %d\n", oYs[i*4+1].y, oYs[i*4+1].p, oYs[i*4+1].k, oYs[i*4+1].id, oYs[i*4+1].dist);
printf("%d %d %d %d %d\n", oYs[i*4+3].y, oYs[i*4+3].p, oYs[i*4+3].k, oYs[i*4+3].id, oYs[i*4+3].dist);
}*/
}
