#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
const int MAXN = 4e5+200 ;
const int inf = 1e9+7 ;
using namespace std ;
struct Event
{
// -1 = building opening
// 1 = building closing
int type ;
int y , xMin , xMax ;
Event(int type = 0 , int y = 0 ,int xMin = 0 , int xMax = 0 ) : type(type), y(y) , xMin(xMin), xMax(xMax) {}
bool operator < (Event other) const
{
//Don't care about ties because you will process in batches
return y < other.y ;
}
void print() { printf("%d %d %d %d\n", type, y, xMin, xMax ) ; }
} ;
vector<Event> node ;
vector<bool> vis ;
int S , T , U , V ;
int n ;
int A[MAXN] , B[MAXN] , C[MAXN] , D[MAXN] ;
vector<int> sourceNodes , sinkNodes ;
vector<int> fila , dist ; // for the bfs
map<int,int> mp ;
struct Seg
{
set< pair<int,int> > tree[MAXN*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
void insertLine(int pos, int l, int r , int beg, int en, pair<int,int> myPair )
{
if(l > en || r < beg ) return ;
if( l >= beg && r <= en ) return (void)(tree[pos].insert(myPair) ) ;
insertLine(pos<<1 , l, m(l,r) , beg, en, myPair ) ;
insertLine(pos<<1|1 , m(l,r)+1, r, beg, en, myPair ) ;
}
void runThrough(int pos, int l, int r, int k , int beg, int en )
{
//I have to reach k in the seg
//beg and en serve in the set
auto it = tree[pos].lower_bound( make_pair(beg, -1 ) ) ;
while( it != tree[pos].end() && it->first <= en )
{
if(!vis[it->second] )
{
vis[it->second] = true ;
fila.push_back(it->second) ;
}
it++ ;
}
if( l == r ) return ;
if(k <= m(l,r ) ) runThrough(pos<<1 , l, m(l,r) , k, beg, en ) ;
else runThrough(pos<<1|1 , m(l,r)+1, r, k, beg, en ) ;
}
void goErasing(int pos, int l, int r, int beg, int en, pair<int,int> myPair )
{
if( l > en || r < beg ) return ;
if(l >= beg && r <= en )
{
auto it = tree[pos].find( myPair ) ;
tree[pos].erase(it) ;
return ;
}
goErasing(pos<<1 , l, m(l,r) , beg, en, myPair ) ;
goErasing(pos<<1|1 , m(l,r)+1, r, beg, en, myPair ) ;
}
} seg[2] ;
void solve(int segIdx )
{
//Remember to process in batch
//So I won't mind about ties
vector<Event> sweep ;
set<int> points ;
for(int i = 1 ; i <= n ; i++ )
{
sweep.push_back( Event(-1, C[i] , A[i] , B[i]) ) ;
sweep.push_back( Event(1, D[i] , A[i] , B[i]) ) ;
}
sort(all(sweep) ) ;
points.insert( mp[0] ) ;
points.insert( mp[1e9+7] ) ;
for(int i = 0 ; i < sz(sweep) ; )
{
int j = i ;
while( j < sz(sweep) && sweep[j].y == sweep[i].y )
{
if( sweep[j].type == 1 && sweep[j].xMin != sweep[j].xMax )
{
points.erase( points.find(sweep[j].xMin) ) ;
points.erase( points.find(sweep[j].xMax) ) ;
}
j++ ;
}
j = i ;
while( j < sz(sweep) && sweep[j].y == sweep[i].y )
{
auto lef = points.lower_bound( sweep[j].xMin ) ;
lef-- ;
auto rig = points.upper_bound( sweep[j].xMax ) ;
node.push_back( Event(segIdx, sweep[j].y , *lef, *rig) ) ;
if( sweep[j].xMin == sweep[j].xMax )
{
if(sweep[j].y == C[n-1] && sweep[j].xMin == A[n-1] )
sourceNodes.push_back( sz(node) - 1 ) ;
else sinkNodes.push_back( sz(node) - 1 ) ;
}
j++ ;
}
j = i ;
while(j < sz(sweep) && sweep[j].y == sweep[i].y )
{
if( sweep[j].type == -1 && sweep[j].xMin != sweep[j].xMax)
{
points.insert( sweep[j].xMin ) ;
points.insert( sweep[j].xMax ) ;
}
j++ ;
}
i = j ;
}
}
int main()
{
scanf("%d %d %d %d", &S, &T, &U, &V ) ;
scanf("%d", &n ) ;
for(int i = 1 ; i <= n ; i++ ) scanf("%d %d %d %d", &A[i] , &B[i] , &C[i] , &D[i] ) ;
n++;
A[n] = B[n] = S ;
C[n] = D[n] = T ;
n++ ;
A[n] = B[n] = U ;
C[n] = D[n] = V ;
//Compression time :(
//Never liked it
mp[0] = 0 ;
mp[1e9+7] = 0 ;
for(int i = 1 ; i <= n ; i++ )
{
mp[ A[i] ] = 0 ;
mp[ B[i] ] = 0 ;
mp[ C[i] ] = 0 ;
mp[ D[i] ] = 0 ;
}
int Key = 1 ;
for(auto &e : mp ) e.second = Key++ ;
for(int i = 1 ; i <= n ; i++ )
{
A[i] = mp[A[i]] ;
B[i] = mp[B[i]] ;
C[i] = mp[C[i]] ;
D[i] = mp[D[i]] ;
}
/* printf("Debugging compression\n" ) ;
for(int i = 1 ; i <= n ; i++ ) printf("%d %d %d %d\n", A[i] , B[i], C[i] , D[i] ) ;
printf("\n") ; */
//Supposed orientation
solve(0) ;
//Wrong orientation
for(int i = 1 ; i <= n ; i++ )
{
swap(A[i] , C[i] ) ;
swap(B[i] , D[i] ) ;
}
solve(1) ;
for(int i = 1 ; i <= n ; i++ )
{
swap(A[i] , C[i] ) ;
swap(B[i] , D[i] ) ;
}
int curNode = sz(node) ;
for(int i = 0 ; i < curNode ; i++ )
seg[ node[i].type ].insertLine( 1 , 1 ,Key , node[i].xMin , node[i].xMax , make_pair(node[i].y , i) ) ;
vis.resize( curNode ) ;
dist.resize( curNode ) ;
for(auto e : sourceNodes )
{
bool canReach = false ;
if(node[e].type == 0 )
{
//That means I'm horizontal
if( node[e].y == C[n] && node[e].xMin <= A[n] && node[e].xMax >= A[n] )
canReach = true ;
}
else
{
//I'm vertical
if(node[e].y == A[n] && node[e].xMin <= C[n] && C[n] <= node[e].xMax )
canReach = true ;
}
if(canReach)
{
printf("1\n") ;
return 0 ;
}
fila.push_back( e ) ;
vis[e] = true ;
seg[ node[e].type ].goErasing( 1 , 1, Key , node[e].xMin , node[e].xMax , make_pair(node[e].y, e ) ) ;
}
int ini = 0 ;
while(ini < sz(fila) )
{
int cur = fila[ini++] ;
// printf("Now I am processing " ) ;
// node[cur].print() ;
int last = sz(fila) ;
int toLook = !node[cur].type ;
seg[toLook].runThrough(1,1 , Key , node[cur].y , node[cur].xMin , node[cur].xMax ) ;
for(int i = last ; i < sz(fila) ; i++ )
{
dist[fila[i]] = dist[cur]+1 ;
seg[toLook].goErasing( 1 , 1 , Key, node[fila[i]].xMin, node[fila[i]].xMax, make_pair(node[fila[i]].y, fila[i] ) ) ;
}
}
int ans = inf ;
for(auto e : sinkNodes ) ans = min(ans, dist[e] ) ;
printf("%d\n", ans+1 ) ;
}
