#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct rect
{
int x1,x2,y1,y2;
};
struct segx
{
int x1,x2,y;
bool operator<(const segx& other) const
{
if(x1 != other.x1) return x1<other.x1;
if(x2 != other.x2) return x2<other.x2;
return y<other.y;
}
};
struct segy
{
int y1,y2,x;
bool operator<(const segy& other)
{
return x<other.x;
}
};
struct node;
int cur_vert = 0;
vector<pair<int,bool>> graph[18000000];
bool odw[18000000];
int left_node[18000000];
int right_node[18000000];
vector<segx> x_segs;
vector<segy> y_segs;
int build(int l, int r)
{
int ind = cur_vert;
cur_vert+=2;
if(l==r) return ind;
left_node[ind] = build(l,(l+r)/2);
right_node[ind] = build((l+r)/2+1,r);
graph[left_node[ind]+1].pb({ind+1,0});
graph[right_node[ind]+1].pb({ind+1,0});
return ind;
}
int change_vert(int p, int v, int prev, int l, int r)
{
int ind = cur_vert;
cur_vert += 2;
if(l == r)
{
if(v != -1)
{
graph[ind].pb({v,0});
graph[v].pb({ind+1,1});
}
return ind;
}
if(p <= (l+r)/2)
{
right_node[ind] = right_node[prev];
left_node[ind] = change_vert(p,v,left_node[prev],l,(l+r)/2);
}
else
{
left_node[ind] = left_node[prev];
right_node[ind] = change_vert(p,v,right_node[prev],(l+r)/2+1,r);
}
graph[left_node[ind]+1].pb({ind+1,0});
graph[right_node[ind]+1].pb({ind+1,0});
return ind;
}
void con_seg(int l2, int r2, int v, int l, int r, int vert)
{
if(r < l2 || l > r2) return;
if(l >= l2 && r <= r2)
{
graph[v].pb({vert,1});
graph[vert+1].pb({v,0});
return;
}
con_seg(l2,r2,v,l,(l+r)/2,left_node[vert]);
con_seg(l2,r2,v,(l+r)/2+1,r,right_node[vert]);
}
int bfs(int x1, int y1, int x2, int y2)
{
rep(i,cur_vert) odw[i] = 0;
deque<pii> q;
rep(i,siz(x_segs)) if(x_segs[i].x1 <= x1 && x_segs[i].x2 >= x1 && x_segs[i].y == y1) q.push_front({i,0});
rep(i,siz(y_segs)) if(y_segs[i].y1 <= y1 && y_segs[i].y2 >= y1 && y_segs[i].x == x1) q.push_front({i+siz(x_segs),0});
int ans = 1e9;
while(!q.empty())
{
pii t = q.front();
q.pop_front();
if(odw[t.ff]) continue;
odw[t.ff] = 1;
if(t.ff < siz(x_segs) && x_segs[t.ff].x1 <= x2 && x_segs[t.ff].x2 >= x2 && x_segs[t.ff].y == y2)
{
ans = t.ss+1;
break;
}
if(t.ff >= siz(x_segs) && t.ff < siz(x_segs)+siz(y_segs) && y_segs[t.ff-siz(x_segs)].y1 <= y2 && y_segs[t.ff-siz(x_segs)].y2 >= y2 && y_segs[t.ff-siz(x_segs)].x == x2)
{
ans = t.ss+1;
break;
}
forall(it,graph[t.ff]) if(it.ss == 0) q.push_front({it.ff,t.ss}); else q.push_back({it.ff,t.ss+1});
if(t.ff >= siz(x_segs)+siz(y_segs))
{
if(t.ff % 2 == 0)
{
if(left_node[t.ff] != 0)
{
q.push_front({left_node[t.ff],t.ss});
q.push_front({right_node[t.ff],t.ss});
}
}
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
int n;
cin >> n;
vector<rect> rects(n);
rep(i,n) cin >> rects[i].x1 >> rects[i].x2 >> rects[i].y1 >> rects[i].y2;
map<int,int> mx;
map<int,int> my;
mx[x1] = 1;
mx[x2] = 1;
my[y1] = 1;
my[y2] = 1;
forall(it,rects)
{
mx[it.x1] = 1;
mx[it.x2] = 1;
my[it.y1] = 1;
my[it.y2] = 1;
}
int cur = 1;
forall(it,mx) mx[it.ff] = cur++;
cur = 1;
forall(it,my) my[it.ff] = cur++;
x1 = mx[x1];
x2 = mx[x2];
y1 = my[y1];
y2 = my[y2];
forall(it,rects)
{
it.x1 = mx[it.x1];
it.x2 = mx[it.x2];
it.y1 = my[it.y1];
it.y2 = my[it.y2];
}
vector<pii> seg_points;
seg_points.pb({x1,y1});
seg_points.pb({x2,y2});
forall(it,rects)
{
seg_points.pb({it.x1,it.y1});
seg_points.pb({it.x2,it.y2});
}
vector<pair<int,pii>> bor;
// calc_y
forall(it,rects)
{
if(it.x2-it.x1 <= 1) continue;
bor.pb({it.x1+1,{it.y1,1}});
bor.pb({it.x2,{it.y1,-1}});
bor.pb({it.x1+1,{it.y2,1}});
bor.pb({it.x2,{it.y2,-1}});
}
sort(all(bor));
sort(all(seg_points));
set<int> bor_set;
int cur_bor = 0;
forall(it,seg_points)
{
while(cur_bor < siz(bor) && bor[cur_bor].ff <= it.ff)
{
if(bor[cur_bor].ss.ss == 1) bor_set.insert(bor[cur_bor].ss.ff);
else bor_set.erase(bor[cur_bor].ss.ff);
cur_bor++;
}
int prv = 0;
int nxt = siz(my)+2;
auto nxt_ptr = bor_set.lower_bound(it.ss);
if(nxt_ptr != bor_set.end()) nxt = *nxt_ptr;
if(nxt_ptr != bor_set.begin()) prv = *(--nxt_ptr);
y_segs.pb({prv,nxt,it.ff});
}
// calc_x
bor = {};
forall(it,rects)
{
if(it.y2-it.y1 <= 1) continue;
bor.pb({it.y1+1,{it.x1,1}});
bor.pb({it.y2,{it.x1,-1}});
bor.pb({it.y1+1,{it.x2,1}});
bor.pb({it.y2,{it.x2,-1}});
}
sort(all(bor));
forall(it,seg_points) swap(it.ff,it.ss);
sort(all(seg_points));
forall(it,seg_points) swap(it.ff,it.ss);
bor_set = {};
cur_bor = 0;
forall(it,seg_points)
{
while(cur_bor < siz(bor) && bor[cur_bor].ff <= it.ss)
{
if(bor[cur_bor].ss.ss == 1) bor_set.insert(bor[cur_bor].ss.ff);
else bor_set.erase(bor[cur_bor].ss.ff);
cur_bor++;
}
int prv = 0;
int nxt = siz(mx)+2;
auto nxt_ptr = bor_set.lower_bound(it.ff);
if(nxt_ptr != bor_set.end()) nxt = *nxt_ptr;
if(nxt_ptr != bor_set.begin()) prv = *(--nxt_ptr);
x_segs.pb({prv,nxt,it.ss});
}
set<segx> pom;
forall(it,x_segs) pom.insert(it);
x_segs = {};
forall(it,pom) x_segs.pb(it);
cur_vert = siz(x_segs)+siz(y_segs);
if(cur_vert%2 == 1) cur_vert++;
vector<pair<int,pii>> events;
rep(i,siz(x_segs))
{
events.pb({x_segs[i].x1,{i,1}});
events.pb({x_segs[i].x2+1,{i,-1}});
}
sort(all(events));
sort(all(y_segs));
int cur_event = 0;
int tree_ = build(0,(1<<19)-1);
int cur_y = siz(x_segs);
forall(it,y_segs)
{
while(cur_event < siz(events) && events[cur_event].ff <= it.x)
{
int v = events[cur_event].ss.ff;
if(events[cur_event].ss.ss == 1)
{
int new_tree = change_vert(x_segs[v].y,v,tree_,0,(1<<19)-1);
tree_ = new_tree;
}
else
{
int new_tree = change_vert(x_segs[v].y,-1,tree_,0,(1<<19)-1);
tree_ = new_tree;
}
cur_event++;
}
con_seg(it.y1,it.y2,cur_y,0,(1<<19)-1,tree_);
cur_y++;
}
cout << bfs(x1,y1,x2,y2) << "\n";
}
