#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct rect {
int t, b, l, r;
rect() {}
rect(int tt, int bb, int ll, int rr) : t(tt), b(bb), l(ll), r(rr) {}
};
// v(0) = insert, v(1) = delete, v(2) = query
struct eve {
int v, t, l, r;
eve() {}
eve(int vv, int tt, int ll, int rr) : v(vv), t(tt), l(ll), r(rr) {}
bool operator < (const eve &a) const {
if (t != a.t) return t < a.t;
return v < a.v;
}
};
struct line {
int d, l, r, i;
line() {}
line(int dd, int ll, int rr, int ii = 0) : d(dd), l(ll), r(rr), i(ii) {}
bool operator < (const line &a) const {
if (d != a.d) return d < a.d;
if (l != a.l) return l < a.l;
return r < a.r;
}
bool operator == (const line &a) const {
return d == a.d && l == a.l && r == a.r;
}
};
struct segtree {
int n;
vector<set<line>> t;
segtree() {}
segtree(int sz) {
n = max(2, sz);
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n);
}
void add(const line &a) {
add(a, 0, 0, 0, n - 1);
}
void erase(const line &a) {
add(a, 1, 0, 0, n - 1);
}
void add(const line &a, int type, int node, int nl, int nr) {
if (a.r < nl || nr < a.l) return;
if (a.l <= nl && nr <= a.r) {
if (type == 0) t[node].insert(a);
else t[node].erase(a);
return;
}
int mid = (nl + nr) / 2;
add(a, type, 2 * node + 1, nl, mid);
add(a, type, 2 * node + 2, mid + 1, nr);
}
line getrid(const line &a) {
erase(a);
return a;
}
line query(const line &a) {
int pos = a.d + n - 1;
set<line>::iterator it;
line S(a.l, 0, 0, 0);
if (OO) {
cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
cout << "in:\n";
for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
}
it = t[pos].lower_bound(S);
if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
pos = (pos - 1) / 2;
while (pos) {
if (OO) {
cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
cout << "in:\n";
for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
}
it = t[pos].lower_bound(S);
if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
pos = (pos - 1) / 2;
}
if (OO) {
cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
cout << "in:\n";
for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
}
it = t[pos].lower_bound(S);
if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
return line(-1, -1, -1, -1);
}
};
pair<int, int> st, en;
int n, MX, MY;
vector<rect> r;
vector<line> V, H;
segtree TV, TH;
vector<int> dv, dh;
void compress() {
vector<int> compx, compy;
compx.reserve(2 * n + 2);
compy.reserve(2 * n + 2);
compx.push_back(st.first), compx.push_back(en.first);
compy.push_back(st.second), compy.push_back(en.second);
for (auto &i : r) {
compx.push_back(i.l), compx.push_back(i.r);
compy.push_back(i.b), compy.push_back(i.t);
}
sort(compx.begin(), compx.end());
sort(compy.begin(), compy.end());
compx.resize(unique(compx.begin(), compx.end()) - compx.begin());
compy.resize(unique(compy.begin(), compy.end()) - compy.begin());
auto MP = [](const vector<int> &aa, int &value) {
value = lower_bound(aa.begin(), aa.end(), value) - aa.begin();
};
MP(compx, st.first), MP(compx, en.first);
MP(compy, st.second), MP(compy, en.second);
for (auto &i : r) {
MP(compx, i.l), MP(compx, i.r);
MP(compy, i.b), MP(compy, i.t);
}
MX = compx.size();
MY = compy.size();
}
void calc_vertical() {
vector<eve> E;
E.reserve(4 * n + 2);
E.push_back(eve(2, st.first, st.second, st.second));
E.push_back(eve(2, en.first, en.second, en.second));
for (auto &i : r) {
E.push_back(eve(0, i.l + 1, i.b, i.t));
E.push_back(eve(2, i.l, i.b, i.b));
E.push_back(eve(1, i.r, i.b, i.t));
E.push_back(eve(2, i.r, i.b, i.b));
}
sort(E.begin(), E.end());
set<pair<int, int>> bl;
for (const auto &i : E) {
if (i.v == 0)
bl.insert({ i.l, i.r });
else if (i.v == 1)
bl.erase({ i.l, i.r });
else {
int lo, hi;
auto it = bl.lower_bound({ i.l,i.l });
if (it == bl.end()) hi = MY - 1;
else hi = it->first;
if (it == bl.begin()) lo = 0;
else {
it--;
lo = it->second;
}
V.push_back(line(i.t, lo, hi));
}
}
V.push_back(line(0, 0, MY - 1));
V.push_back(line(MX - 1, 0, MY - 1));
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
for (int i = 0; i < V.size(); i++) V[i].i = i;
}
void calc_horizontal() {
vector<eve> E;
E.reserve(3 * n + 2);
E.push_back(eve(2, st.second, st.first, st.first));
E.push_back(eve(2, en.second, en.first, en.first));
for (auto &i : r) {
E.push_back(eve(0, i.b + 1, i.l, i.r));
E.push_back(eve(2, i.b, i.l, i.l));
E.push_back(eve(1, i.t, i.l, i.r));
E.push_back(eve(2, i.t, i.l, i.l));
}
sort(E.begin(), E.end());
set<pair<int, int>> bl;
for (const auto &i : E) {
if (i.v == 0)
bl.insert({ i.l, i.r });
else if (i.v == 1)
bl.erase({ i.l, i.r });
else {
int lo, hi;
auto it = bl.lower_bound({ i.l,i.l });
if (it == bl.end()) hi = MX - 1;
else hi = it->first;
if (it == bl.begin()) lo = 0;
else {
it--;
lo = it->second;
}
H.push_back(line(i.t, lo, hi));
}
}
H.push_back(line(0, 0, MX - 1));
H.push_back(line(MY - 1, 0, MX - 1));
sort(H.begin(), H.end());
H.resize(unique(H.begin(), H.end()) - H.begin());
for (int i = 0; i < H.size(); i++) H[i].i = i;
}
void bfs(int startv, int starth) {
dv.resize(V.size(), -1);
dh.resize(H.size(), -1);
dv[startv] = dh[starth] = 0;
TV.erase(V[startv]);
TH.erase(H[starth]);
queue<pair<int, int>> q;
q.push({ startv, 0 });
q.push({ starth, 1 });
while (q.size()) {
pair<int, int> x = q.front();
q.pop();
if (OO) {
cout << "bfs on " << x.first << " " << x.second << '\n';
cout << "with distance ";
if (x.second == 0) cout << dv[x.first] << '\n';
else cout << dh[x.first] << '\n';
}
if (x.second == 0) {
// current is vertical
line c = TH.query(V[x.first]);
while (c.d != -1) {
dh[c.i] = 1 + dv[x.first];
q.push({ c.i, 1 });
c = TH.query(V[x.first]);
}
}
else {
line c = TV.query(H[x.first]);
while (c.d != -1) {
dv[c.i] = 1 + dh[x.first];
q.push({ c.i, 0 });
c = TV.query(H[x.first]);
}
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> st.first >> st.second >> en.first >> en.second;
cin >> n;
r.resize(n);
for (auto &i : r) cin >> i.l >> i.r >> i.b >> i.t;
compress();
calc_vertical();
calc_horizontal();
if (OO) {
cout << "start " << st.first << " " << st.second << '\n';
cout << "end " << en.first << " " << en.second << '\n';
cout << "rectangles\n";
for (const auto &i : r) {
cout << i.l << " " << i.b << " " << i.r << " " << i.t << '\n';
}
cout << "verticals\n";
for (const auto &i : V) cout << i.d << ", [" << i.l << " " << i.r << "]\n";
cout << "horizontals\n";
for (const auto &i : H) cout << i.d << ", [" << i.l << " " << i.r << "]\n";
}
TV = segtree(MY);
TH = segtree(MX);
for (const auto &i : V) TV.add(i);
for (const auto &i : H) TH.add(i);
int starth, startv, endh, endv;
for (const auto &i : V) {
if (i.d == st.first && i.l <= st.second && st.second <= i.r) startv = i.i;
if (i.d == en.first && i.l <= en.second && en.second <= i.r) endv = i.i;
}
for (const auto &i : H) {
if (i.d == st.second && i.l <= st.first && st.first <= i.r) starth = i.i;
if (i.d == en.second && i.l <= en.first && en.first <= i.r) endh = i.i;
}
bfs(startv, starth);
cout << 1 + min(dv[endv], dh[endh]) << '\n';
}
