#line 1 "main.cpp"
/**
* @title Template
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <deque>
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"
class range {
struct iter {
std::size_t itr;
constexpr iter(std::size_t pos) noexcept: itr(pos) { }
constexpr void operator ++ () noexcept { ++itr; }
constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
constexpr std::size_t operator * () const noexcept { return itr; }
};
struct reviter {
std::size_t itr;
constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
constexpr void operator ++ () noexcept { --itr; }
constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
constexpr std::size_t operator * () const noexcept { return itr; }
};
const iter first, last;
public:
constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
constexpr iter begin() const noexcept { return first; }
constexpr iter end() const noexcept { return last; }
constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }
constexpr reviter rend() const noexcept { return reviter(*first - 1); }
};
/**
* @title Range
*/
#line 17 "main.cpp"
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;
template <class T>
using Vec = std::vector<T>;
struct Compressor {
Vec<i32> data;
Compressor(const usize size = 0) {
data.reserve(size);
}
void add(const i32 x) {
data.push_back(x);
}
void compress() {
std::sort(data.begin(), data.end());
data.erase(std::unique(data.begin(), data.end()), data.end());
}
i32 fix(const i32 x) const {
return std::lower_bound(data.begin(), data.end(), x) - data.begin();
}
usize size() const {
return data.size();
}
};
int main() {
i32 S, T, U, V;
std::cin >> S >> T >> U >> V;
usize N;
std::cin >> N;
Compressor Xc(2 * N + 4), Yc(2 * N + 4);
Xc.add(S);
Xc.add(U);
Xc.add(0);
Xc.add(1000000001);
Yc.add(T);
Yc.add(V);
Yc.add(0);
Yc.add(1000000001);
Vec<i32> A(N), B(N), C(N), D(N);
for (auto i: range(0, N)) {
std::cin >> A[i] >> B[i] >> C[i] >> D[i];
Xc.add(A[i]);
Xc.add(B[i]);
Yc.add(C[i]);
Yc.add(D[i]);
}
Xc.compress();
Yc.compress();
S = Xc.fix(S);
U = Xc.fix(U);
T = Yc.fix(T);
V = Yc.fix(V);
for (auto i: range(0, N)) {
A[i] = Xc.fix(A[i]);
B[i] = Xc.fix(B[i]);
C[i] = Yc.fix(C[i]);
D[i] = Yc.fix(D[i]);
}
Vec<Vec<isize>> block(Xc.size(), Vec<isize>(Yc.size()));
for (auto i: range(0, N)) {
block[A[i]][C[i]] += 1;
block[A[i]][D[i]] -= 1;
block[B[i]][C[i]] -= 1;
block[B[i]][D[i]] += 1;
}
for (auto i: range(0, Xc.size())) {
for (auto j: range(0, Yc.size())) {
if (i > 0) {
block[i][j] += block[i - 1][j];
}
if (j > 0) {
block[i][j] += block[i][j - 1];
}
if (i > 0 && j > 0) {
block[i][j] -= block[i - 1][j - 1];
}
}
}
Vec<Vec<std::array<usize, 4>>> dist(Xc.size(), Vec<std::array<usize, 4>>(Yc.size()));
for (auto &a: dist) {
for (auto &b: a) {
b.fill(inf32);
}
}
std::deque<std::tuple<usize, usize, isize>> que;
const auto push = [&](const usize x, const usize y, const usize k, const usize d, const bool to_back) {
if (dist[x][y][k] > d) {
dist[x][y][k] = d;
if (to_back) {
que.emplace_back(x, y, k);
}
else {
que.emplace_front(x, y, k);
}
}
};
for (auto k: range(0, 4)) {
push(S, T, k, 1, true);
}
while (!que.empty()) {
const auto [x, y, k] = que.front();
que.pop_front();
std::array<usize, 4> next;
next.fill(dist[x][y][k] + 1);
next[k] -= 1;
if (x + 1 != Xc.size()) {
if (block[x][y] == 0 || (y > 0 && block[x][y - 1] == 0)) {
push(x + 1, y, 0, next[0], k != 0);
}
}
if (x > 0) {
if (block[x - 1][y] == 0 || (y > 0 && block[x - 1][y - 1] == 0)) {
push(x - 1, y, 1, next[1], k != 1);
}
}
if (y + 1 != Yc.size()) {
if (block[x][y] == 0 || (x > 0 && block[x - 1][y] == 0)) {
push(x, y + 1, 2, next[2], k != 2);
}
}
if (y > 0) {
if (block[x][y - 1] == 0 || (x > 0 && block[x - 1][y - 1] == 0)) {
push(x, y - 1, 3, next[3], k != 3);
}
}
}
usize ans = inf32;
for (auto k: range(0, 4)) {
ans = std::min(ans, dist[U][V][k]);
}
std::cout << ans << '\n';
return 0;
}
