#include <bits/stdc++.h>
using namespace std;
const int U_MAX = 45678999;
const int MAX = 262144;
int sum[U_MAX], left_son[U_MAX], right_son[U_MAX];
struct event {
int x, y, type;
event(int a, int b, int t): x(a), y(b), type(t) {
}
bool operator <(const event &a) const {
if (x != a.x) {
return x < a.x;
} else if (type != a.type) {
return type < a.type;
} else {
return y < a.y;
}
}
};
struct range {
int x, L, R;
range(int a, int l, int r): x(a), L(l), R(r) {
}
};
int main() {
do {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
} while (false);
int n, sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
cin >> n;
vector<int> vec_x, vec_y;
auto add_point = [&] (int x, int y) {
vec_x.push_back(x);
vec_y.push_back(y);
};
add_point(sx, sy);
add_point(tx, ty);
vector<int> xl(n), yl(n), xr(n), yr(n);
for (int i = 0; i < n; i++) {
cin >> xl[i] >> xr[i] >> yl[i] >> yr[i];
add_point(xl[i], yl[i]);
add_point(xr[i], yr[i]);
}
auto normalize = [&] (vector<int> &vec) {
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
};
normalize(vec_x);
normalize(vec_y);
auto get_idx_x = [&] (int &x) {
x = lower_bound(vec_x.begin(), vec_x.end(), x) - vec_x.begin() + 1;
};
auto get_idx_y = [&] (int &y) {
y = lower_bound(vec_y.begin(), vec_y.end(), y) - vec_y.begin() + 1;
};
get_idx_x(sx);
get_idx_y(sy);
get_idx_x(tx);
get_idx_y(ty);
for (int i = 0; i < n; i++) {
get_idx_x(xl[i]);
get_idx_y(yl[i]);
get_idx_x(xr[i]);
get_idx_y(yr[i]);
}
int node_cnt = 0;
function<int (int &, int, int, int, int)> add_in = [&] (int &u, int l, int r, int qx, int qy) {
if (!u) {
node_cnt++;
u = node_cnt;
}
if (l == r) {
if (sum[u]) {
return 0;
} else {
sum[u] = qy + 1;
return 1;
}
} else {
int mid = (l + r) / 2, result = 0;
if (qx <= mid) {
result = add_in(left_son[u], l, mid, qx, qy);
} else {
result = add_in(right_son[u], mid + 1, r, qx, qy);
}
sum[u] += result;
return result;
}
};
function<void (vector<int> &, int, int, int, int, int, int, int)> add_out = [&] (vector<int> &root, int u, int l, int r, int ql, int qr, int qx, int qy) {
if (l == ql && r == qr) {
add_in(root[u], 0, MAX - 1, qx, qy);
} else {
int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
if (qr <= mid) {
add_out(root, x, l, mid, ql, qr, qx, qy);
} else if (ql > mid) {
add_out(root, y, mid + 1, r, ql, qr, qx, qy);
} else {
add_out(root, x, l, mid, ql, mid, qx, qy);
add_out(root, y, mid + 1, r, mid + 1, qr, qx, qy);
}
}
};
auto init = [&] (vector<int> &root) {
vector<event> eve;
eve.emplace_back(sx, sy, 0);
eve.emplace_back(tx, ty, 0);
for (int i = 0; i < n; i++) {
eve.emplace_back(xl[i], yl[i], 1);
eve.emplace_back(xl[i], yr[i], 1);
eve.emplace_back(xr[i], yl[i], -1);
eve.emplace_back(xr[i], yr[i], -1);
eve.emplace_back(xl[i], yl[i], 0);
eve.emplace_back(xr[i], yl[i], 0);
}
sort(eve.begin(), eve.end());
set<int> important;
important.insert(0);
important.insert(MAX - 1);
vector<range> result;
for (auto e : eve) {
int x = e.x, y = e.y, type = e.type;
if (type == 1) {
important.insert(y);
} else if (type == -1) {
important.erase(y);
} else {
auto it = important.upper_bound(y);
int R = *it, L = *--it;
add_out(root, 0, 0, MAX - 1, L, R, x, result.size());
result.emplace_back(x, L, R);
}
}
return result;
};
auto reverse_xy = [&] () {
swap(sx, sy);
swap(tx, ty);
swap(xl, yl);
swap(xr, yr);
};
vector<int> root_x(MAX * 2), root_y(MAX * 2);
auto range_x = init(root_x);
reverse_xy();
auto range_y = init(root_y);
reverse_xy();
vector<int> dis_x(range_x.size(), INT_MAX), dis_y(range_y.size(), INT_MAX);
queue<pair<int, int> > que;
for (int i = 0; i < range_x.size(); i++) {
if (range_x[i].x == sx && sy >= range_x[i].L && sy <= range_x[i].R) {
dis_x[i] = 1;
que.emplace(i, 0);
}
}
for (int i = 0; i < range_y.size(); i++) {
if (range_y[i].x == sy && sx >= range_y[i].L && sx <= range_y[i].R) {
dis_y[i] = 1;
que.emplace(i, 1);
}
}
function<int (int, int, int, int, int, int, int)> fast_in = [&] (int u, int l, int r, int ql, int qr, int qv, int xy) {
if (!u || !sum[u]) {
return 0;
} else if (l == r) {
int v = sum[u] - 1;
auto &dis = xy ? dis_x : dis_y;
if (dis[v] == INT_MAX) {
dis[v] = qv;
que.emplace(v, !xy);
}
sum[u] = 0;
return 1;
} else {
int mid = (l + r) / 2, result = 0;
if (qr <= mid) {
result += fast_in(left_son[u], l, mid, ql, qr, qv, xy);
} else if (mid < ql) {
result += fast_in(right_son[u], mid + 1, r, ql, qr, qv, xy);
} else {
result += fast_in(left_son[u], l, mid, ql, mid, qv, xy);
result += fast_in(right_son[u], mid + 1, r, mid + 1, qr, qv, xy);
}
sum[u] -= result;
return result;
}
};
function<void (vector<int> &, int, int, int, int, int, int, int, int)> fast_out = [&] (vector<int> &root, int u, int l, int r, int pos, int ql, int qr, int qv, int xy) {
fast_in(root[u], 0, MAX - 1, ql, qr, qv, xy);
if (l == r) {
return;
} else {
int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
if (pos <= mid) {
fast_out(root, x, l, mid, pos, ql, qr, qv, xy);
} else {
fast_out(root, y, mid + 1, r, pos, ql, qr, qv, xy);
}
}
};
while (!que.empty()) {
int u = que.front().first, xy = que.front().second;
que.pop();
if (xy == 0) {
if (range_x[u].x == tx && ty >= range_x[u].L && ty <= range_x[u].R) {
cout << dis_x[u] << endl;
return 0;
} else {
fast_out(root_y, 0, 0, MAX - 1, range_x[u].x, range_x[u].L, range_x[u].R, dis_x[u] + 1, 0);
}
} else {
if (range_y[u].x == ty && tx >= range_y[u].L && tx <= range_y[u].R) {
cout << dis_y[u] << endl;
return 0;
} else {
fast_out(root_x, 0, 0, MAX - 1, range_y[u].x, range_y[u].L, range_y[u].R, dis_y[u] + 1, 1);
}
}
}
return 0;
}
