#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int N = 1e5 + 10;
vector<int> rrhx, rrhy;
int st_x, st_y, ed_x, ed_y, n, m;
tuple<int, int, int> line[N << 2];
int d[N << 2];
queue<int> q;
struct IT {
set<pair<int, int> > T[N << 3];
void up(int s, int l, int r, int from, int to, pair<int, int> val) {
if (l > to || r < from) return;
if (from <= l && r <= to) {
T[s].insert(val);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
}
void get (int s, int l, int r, int pos, int from, int to, int val) {
while (!T[s].empty()) {
auto it = T[s].lower_bound(make_pair(from, 0));
if (it == T[s].end()) break;
if (it -> first > to) break;
if (d[it -> second] == 0) {
d[it -> second] = val;
q.push(it -> second);
}
T[s].erase(it);
}
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) get(s << 1, l, mid, pos, from, to, val);
else get(s << 1 | 1, mid + 1, r, pos, from, to, val);
}
} itx, ity;
struct square {
int x1, x2, y1, y2;
};
square rect[N];
vector<tuple<int, int, int> > expand (vector<pair<int, int> > p) {
vector<tuple<int, int, int> > event;
set<pair<int, int> > s;
for(int i = 1; i <= n; i++) if (rect[i].x1 + 1 < rect[i].x2) {
event.emplace_back(rect[i].x1 + 1, rect[i].y1, rect[i].y2);
event.emplace_back(rect[i].x2, rect[i].y1, rect[i].y2);
// cout << rect[i].x1 + 1 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
// cout << rect[i].x2 - 1 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
}
for(auto &[x, y] : p) {
event.emplace_back(x, y, 0);
// cout << x << " " << y << endl;
}
sort(all(event), [] (const tuple<int, int, int> &x, const tuple<int, int, int> &y) {
if (get<0> (x) != get<0> (y)) return get<0> (x) < get<0> (y);
return get<2> (x) > get<2> (y);
});
vector<tuple<int, int, int> > ret;
for(auto &[x, y, z] : event) {
if (z == 0) {
auto it = s.lower_bound(make_pair(y, y));
int l = 1, r = m;
// cout << x << " " << y << " " << s.size() << endl;
if (it != s.end()) r = it -> first;
if (it != s.begin()) {
it--;
l = it -> second;
}
ret.emplace_back(x, l, r);
}
else {
if (s.empty()) {
s.insert(make_pair(y, z));
}
else {
auto it = s.find(make_pair(y, z));
if (it != s.end()) s.erase(it);
else s.insert(make_pair(y, z));
}
}
}
return ret;
}
int32_t main() {
#define task ""
cin.tie(0) -> sync_with_stdio(0);
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
if (fopen(task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> st_x >> st_y >> ed_x >> ed_y;
cin >> n;
for(int i = 1; i <= n; i++) cin >> rect[i].x1 >> rect[i].x2 >> rect[i].y1 >> rect[i].y2;
rect[0].x1 = st_x; rect[0].y1 = st_y;
rect[0].x2 = ed_x; rect[0].y2 = ed_y;
for(int i = 0; i <= n; i++) {
rrhx.push_back(rect[i].x1);
rrhx.push_back(rect[i].x2);
rrhy.push_back(rect[i].y1);
rrhy.push_back(rect[i].y2);
}
sort(all(rrhx));
rrhx.resize(unique(all(rrhx)) - rrhx.begin());
sort(all(rrhy));
rrhy.resize(unique(all(rrhy)) - rrhy.begin());
m = max(rrhx.size(), rrhy.size());
for(int i = 0; i <= n; i++) {
rect[i].x1 = upper_bound(all(rrhx), rect[i].x1) - rrhx.begin();
rect[i].x2 = upper_bound(all(rrhx), rect[i].x2) - rrhx.begin();
rect[i].y1 = upper_bound(all(rrhy), rect[i].y1) - rrhy.begin();
rect[i].y2 = upper_bound(all(rrhy), rect[i].y2) - rrhy.begin();
}
st_x = rect[0].x1; st_y = rect[0].y1;
ed_x = rect[0].x2; ed_y = rect[0].y2;
// cout << st_x << " " << st_y << " " << ed_x << " " << ed_y << endl;
// for(int i = 1; i <= n; i++) {
// cout << rect[i].x1 << " " << rect[i].x2 << " " << rect[i].y1 << " " << rect[i].y2 << endl;
// }
vector<pair<int, int> > tmp;
tmp.emplace_back(st_x, st_y);
tmp.emplace_back(ed_x, ed_y);
for(int i = 1; i <= n; i++) {
tmp.emplace_back(rect[i].x1, rect[i].y1);
tmp.emplace_back(rect[i].x2, rect[i].y2);
}
vector<tuple<int, int, int> > line1 = expand(tmp);
for(auto &[x, y] : tmp) swap(x, y);
for(int i = 1; i <= n; i++) {
swap(rect[i].x1, rect[i].y1);
swap(rect[i].x2, rect[i].y2);
}
vector<tuple<int, int, int> > line2 = expand(tmp);
for(int i = 1; i <= n; i++) {
swap(rect[i].x1, rect[i].y1);
swap(rect[i].x2, rect[i].y2);
}
int cnt = 0;
for(auto &[x, y1, y2] : line1) {
line[++cnt] = {x, y1, y2};
// cout << x << " " << y1 << " " << y2 << endl;
if (st_x == x && y1 <= st_y && st_y <= y2) {
d[cnt] = 1;
q.push(cnt);
}
else itx.up(1, 1, m, y1, y2, make_pair(x, cnt));
}
int cntx = cnt;
for(auto &[y, x1, x2] : line2) {
line[++cnt] = {y, x1, x2};
// cout << y << " " << x1 << " " << x2 << endl;
if (st_y == y && x1 <= st_x && st_x <= x2) {
d[cnt] = 1;
q.push(cnt);
}
else ity.up(1, 1, m, x1, x2, make_pair(y, cnt));
}
// exit(0);
while (!q.empty()) {
int u = q.front(); q.pop();
if (u <= cntx) {
int x, y1, y2; tie(x, y1, y2) = line[u];
if (ed_x == x && y1 <= ed_y && ed_y <= y2) return cout << d[u], 0;
ity.get(1, 1, m, x, y1, y2, d[u] + 1);
}
else {
int y, x1, x2; tie(y, x1, x2) = line[u];
if (ed_y == y && x1 <= ed_x && ed_x <= x2) return cout << d[u], 0;
itx.get(1, 1, m, y, x1, x2, d[u] + 1);
}
}
}
