#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;
}
};
int cur_vert = 0;
vector<pii> graph[20000000];
int dist[20000000];
vector<segx> x_segs;
vector<segy> y_segs;
struct node
{
int l = 0;
int r = (1<<19)-1;
node* left = NULL;
node* right = NULL;
int vert_ind = 0;
void build()
{
vert_ind = cur_vert;
cur_vert+=2;
if(l==r) return;
left = new node;
left -> l = l;
left -> r = (l+r)/2;
right = new node;
right -> l = (l+r)/2+1;
right -> r = r;
left->build();
right->build();
graph[vert_ind].pb({left->vert_ind,0});
graph[vert_ind].pb({right->vert_ind,0});
graph[right->vert_ind+1].pb({vert_ind+1,0});
graph[left->vert_ind+1].pb({vert_ind+1,0});
}
void change_vert(int p, int v, node* prev)
{
vert_ind = cur_vert;
cur_vert += 2;
if(l == r)
{
if(v != -1)
{
graph[vert_ind].pb({v,0});
graph[v].pb({vert_ind+1,1});
}
return;
}
if(p <= (l+r)/2)
{
right = prev->right;
left = new node;
left -> l = l;
left -> r = (l+r)/2;
left -> change_vert(p,v,prev->left);
}
else
{
left = prev->left;
right = new node;
right -> l = (l+r)/2+1;
right -> r = r;
right -> change_vert(p,v,prev->right);
}
graph[vert_ind].pb({right->vert_ind,0});
graph[right->vert_ind+1].pb({vert_ind+1,0});
graph[vert_ind].pb({left->vert_ind,0});
graph[left->vert_ind+1].pb({vert_ind+1,0});
}
void con_seg(int l2, int r2, int v)
{
if(r < l2 || l > r2) return;
if(l >= l2 && r <= r2)
{
graph[v].pb({vert_ind,1});
graph[vert_ind+1].pb({v,0});
return;
}
left->con_seg(l2,r2,v);
right->con_seg(l2,r2,v);
}
};
int bfs(int x1, int y1, int x2, int y2)
{
rep(i,cur_vert) dist[i] = 1e9;
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});
while(!q.empty())
{
pii t = q.front();
q.pop_front();
if(dist[t.ff] != 1e9) continue;
dist[t.ff] = t.ss;
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});
}
int ans = 1e9;
rep(i,siz(x_segs)) if(x_segs[i].x1 <= x2 && x_segs[i].x2 >= x2 && x_segs[i].y == y2) ans = min(ans,dist[i]+1);
rep(i,siz(y_segs)) if(y_segs[i].y1 <= y2 && y_segs[i].y2 >= y2 && y_segs[i].x == x2) ans = min(ans,dist[i+siz(x_segs)]+1);
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);
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;
node tree_;
tree_.build();
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)
{
node new_tree;
new_tree.change_vert(x_segs[v].y,v,&tree_);
tree_ = new_tree;
}
else
{
node new_tree;
new_tree.change_vert(x_segs[v].y,-1,&tree_);
tree_ = new_tree;
}
cur_event++;
}
tree_.con_seg(it.y1,it.y2,cur_y);
cur_y++;
}
cout << bfs(x1,y1,x2,y2) << "\n";
}
