#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e5+5;
struct seg{
int l,r,y,id;
};
int IT = 0; // each segment gets assigned an id
int dst[maxn * 20 * 4 * 4];
bool dir[maxn * 20 * 4 * 4];
bool NOWHOR = 0;
struct rect{
int x1, x2, y1, y2;
};
int Sx, Sy, Tx, Ty;
vector<seg> who;
vector<seg> get(vector<rect> &v) {
set<int> have; // current y positions
// scan from left to right along x axis
struct Ev{
int x,y;
int id; // id 1: remove, id 2: ask, id 3: add
bool operator < (Ev & o) {
return x != o.x? x < o.x : id < o.id;
}
};
vector<Ev> ev;
ev.pb({Sx, Sy, 2});
ev.pb({Tx, Ty, 2});
for (rect r : v) {
ev.pb({r.x1, r.y1, 3});
ev.pb({r.x1, r.y2, 3});
ev.pb({r.x1, r.y1, 2});
ev.pb({r.x2, r.y1, 2});
ev.pb({r.x2, r.y1, 1});
ev.pb({r.x2, r.y2, 1});
}
sort(ALL(ev));
vector<seg> ret;
set<pair<pii, int> > seghave;
for (Ev & e : ev) {
if (e.id == 1) {
have.erase(e.y);
}
if (e.id == 3) {
have.insert(e.y);
}
if (e.id == 2) {
auto it = have.lower_bound(e.y);
int ybig = it==have.end()?iinf : *it;
int ysmall = it==have.begin()? 0 : *prev(it);
if (seghave.count({{ysmall, ybig}, e.x})) {
continue;
}
seghave.insert({{ysmall, ybig}, e.x});
dir[IT] = NOWHOR;
ret.pb({ysmall, ybig, e.x, IT++});
}
}
return ret;
}
queue<int> qq;
struct smolseg{
vector<pii> s;
vector<int> id;
void build(int o, int l, int r) {
bug(o,l,r);
if (l > r) return;
if (l == r) {
id[o] = s[l].s;
return;
}
dir[IT] = NOWHOR;
id[o] = IT++;
int mid = (l+r)/2;
build(o*2,l,mid); build(o*2+1, mid+1,r);
}
void build(){
sort(ALL(s));
id.resize(SZ(s) * 4);
build(1,0,SZ(s)-1);
}
void runupd(int L, int R, int d, int o, int l, int r) {
if (l > r) return;
if (s[l].f > R || s[r].f < L) return;
int mid = (l+r)/2;
if (s[l].f >= L && s[r].f <= R) {
if (dst[id[o]] <= d) {
return;
}
dst[id[o]] = d;
if (l == r) {
qq.push(id[o]);
return;
}
}
runupd(L,R,d,o*2,l,mid);
runupd(L,R,d,o*2+1,mid+1,r);
}
void runupd(int L, int R, int d) {
runupd(L,R,d,1,0,SZ(s)-1);
}
};
struct STree{
int MX;
smolseg s[maxn*4*3]; // y position, index
void put(int L, int R, pii v, int o=1, int l=0, int r=-1) {
if (r == -1) r = MX-1;
if (l > R || r < L) return;
if (l >= L && r <= R) {
s[o].s.pb(v); return;
}
int mid = (l+r)/2;
put(L,R,v,o*2,l,mid);
put(L,R,v,o*2+1,mid+1,r);
}
void build(int o, int l, int r){
s[o].build();
if (l!=r) {
int mid = (l+r)/2;
build(o*2, l,mid);
build(o*2+1, mid+1,r);
}
}
void run(seg S, int o=1, int l=0, int r=-1) {
if (r == -1) r = MX-1;
if (r < S.y || l > S.y) return;
s[o].runupd(S.l, S.r, dst[S.id]+1);
if (l == r) return;
int mid = (l+r)/2;
run(S,o*2,l,mid); run(S,o*2+1,mid+1,r);
}
}AA[2]; // this is the big, scary segment tree you were waiting for!!!!!
signed main(){
IOS();
cin>>Sx>>Sy>>Tx>>Ty;
int n; cin>>n;
vector<rect> v;
REP(i,n) {
int x1,x2,y1,y2;
cin>>x1>>x2>>y1>>y2;
v.pb({x1,x2,y1,y2});
}
NOWHOR = 0;
vector<seg> gver = get(v); // gver returns vertical lines
for (auto &r : v) {
swap(r.x1, r.y1);
swap(r.x2, r.y2);
}
swap(Sx, Sy); swap(Tx, Ty);
NOWHOR = 1;
vector<seg> ghor = get(v);
for (auto &r : v) {
swap(r.x1, r.y1);
swap(r.x2, r.y2);
}
swap(Sx, Sy); swap(Tx, Ty);
for (auto s : gver) {
bug(s.y, s.l, s.r);
}
// step 2: compress coordinates
vector<int> posx, posy;
for (auto s : gver) {
posy.pb(s.l);
posy.pb(s.r);
posx.pb(s.y);
}
for (auto s : ghor) {
posx.pb(s.l);
posx.pb(s.r);
posy.pb(s.y);
}
SORT_UNIQUE(posx); SORT_UNIQUE(posy);
who.resize(IT);
for (auto &s : gver) {
s.l = lower_bound(ALL(posy), s.l) - posy.begin();
s.r = lower_bound(ALL(posy), s.r) - posy.begin();
s.y = lower_bound(ALL(posx), s.y) - posx.begin();
who[s.id] = s;
}
for (auto &s : ghor) {
s.l = lower_bound(ALL(posx), s.l) - posx.begin();
s.r = lower_bound(ALL(posx), s.r) - posx.begin();
s.y = lower_bound(ALL(posy), s.y) - posy.begin();
who[s.id] = s;
}
Sx = lower_bound(ALL(posx), Sx) - posx.begin();
Tx = lower_bound(ALL(posx), Tx) - posx.begin();
Sy = lower_bound(ALL(posy), Sy) - posy.begin();
Ty = lower_bound(ALL(posy), Ty) - posy.begin();
// step 3: build the segtree layers
NOWHOR = 0;
AA[0].MX = SZ(posy);
for (auto &s : gver) { // AA[0] stores the vertical ones
AA[0].put(s.l, s.r, make_pair(s.y, s.id));
}
AA[0].build(1,0,SZ(posy)-1);
NOWHOR = 1;
AA[1].MX = SZ(posx);
for (auto &s : ghor) { // AA[1] stores the horizontal ones
AA[1].put(s.l, s.r, make_pair(s.y, s.id));
}
AA[1].build(1,0,SZ(posx)-1);
// step 4: run the bfs
memset(dst, 0x3f, sizeof dst);
for (auto & s : gver) {
if (s.y == Sx && (s.l <= Sy && Sy <= s.r)) {
bug(s.id);
bug(s.y,s.l,s.r,dst[s.id]);
qq.push(s.id);
dst[s.id] = 0;
}
}
for (auto & s : ghor) {
if (s.y == Sy && (s.l <= Sx && Sx <= s.r)) {
bug(s.id);
bug("p2", s.y,s.l,s.r,dst[s.id]);
qq.push(s.id);
dst[s.id] = 0;
}
}
while (!qq.empty()) {
int v = qq.front(); qq.pop();
bug(v, dst[v]);
bug(dir[v], who[v].l, who[v].r);
bug(who[v].y);
AA[dir[v]^1].run(who[v]);
}
int re = 0x3f3f3f3f;
for (auto & s : gver) {
if (s.y == Tx && (s.l <= Ty && Ty <= s.r)) {
bug(s.id);
bug(s.y,s.l,s.r,dst[s.id]);
MN(re, dst[s.id]);
}
}
for (auto & s : ghor) {
if (s.y == Ty && (s.l <= Tx && Tx <= s.r)) {
bug(s.id);
bug("p2", s.y,s.l,s.r,dst[s.id]);
MN(re, dst[s.id]);
}
}
cout<<re+1<<endl;
}
