OI XXIV - zam

// https://szkopul.edu.pl/problemset/problem/7Lmwi_qxvuplTPlhRuci1UBt/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

struct Point {
    int x, y;
};

constexpr int INF = 1e9 + 7;

std::vector<int> kra[sizik];
std::bitset<sizik> cannot;

struct BfsItem {
    int v, d;
};

std::bitset<sizik> visited;

int bfs(int start_idx, int end_idx) {
    if (start_idx == end_idx) return 0;

    std::queue<BfsItem> q;
    visited[start_idx] = true;
    q.push({start_idx, 0});

    while (!q.empty()) {
        auto c = q.front();
        q.pop();

        if (c.v == end_idx) {
            return c.d;
        }

        for (const auto& u : kra[c.v]) {
            if (!cannot[u] && !visited[u]) {
                visited[u] = true;
                q.push({u, c.d + 1});
            }
        }
    }
    return -1;
}

constexpr int ROOM_END = 1, ROOM_START = 2, POINT = 3;
constexpr int DANGER_POINT = 4, START_POINT = 5, END_POINT = 6;

struct Event {
    int x, y1, y2, type, id;
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        return type < o.type;
    }
};

struct Interval {
    int y1, y2, id;
    bool operator<(const Interval& o) const {
        if (y1 != o.y1) return y1 < o.y1;
        return id < o.id;
    }
};

struct Room {
    int x1, y1, x2, y2;
};

Room rooms[sizik];

using Wall = ar<int, 5>;

void match(const std::vector<Wall>& L, const std::vector<Wall>& R) {
    int i = 0, j = 0;
    while (i < (int)L.size() && j < (int)R.size()) {
        if (std::max(L[i][1], R[j][1]) < std::min(L[i][2], R[j][2])) {
            kra[L[i][3]].push_back(R[j][3]);
            kra[R[j][3]].push_back(L[i][3]);
        }
        if (L[i][2] < R[j][2]) {
            i++;
        } else if (R[j][2] < L[i][2]) {
            j++;
        } else {
            i++;
            j++;
        }
    }
}

void process_walls(std::vector<Wall>& walls) {
    std::sort(walls.begin(), walls.end(), [](const Wall& a, const Wall& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    });

    std::vector<Wall> L, R;
    int ptr = 0;
    int sz = walls.size();
    while (ptr < sz) {
        int cur_coord = walls[ptr][0];
        L.clear();
        R.clear();
        while (ptr < sz && walls[ptr][0] == cur_coord) {
            if (walls[ptr][4] == 0) {
                L.push_back(walls[ptr]);
            } else {
                R.push_back(walls[ptr]);
            }
            ptr++;
        }
        match(L, R);
    }
}

void solve() {
    int w, h, n, m;
    std::cin >> w >> h >> n >> m;

    Point p, s;
    std::cin >> p.x >> p.y >> s.x >> s.y;

    for (int i = 1; i <= n; i++) {
        std::cin >> rooms[i].x1 >> rooms[i].y1 >> rooms[i].x2 >> rooms[i].y2;

        if (rooms[i].x1 > rooms[i].x2) std::swap(rooms[i].x1, rooms[i].x2);
        if (rooms[i].y1 > rooms[i].y2) std::swap(rooms[i].y1, rooms[i].y2);
    }

    std::vector<Wall> walls;
    walls.reserve(2 * n);
    for (int i = 1; i <= n; i++) {
        walls.push_back({rooms[i].x2, rooms[i].y1, rooms[i].y2, i, 0});
        walls.push_back({rooms[i].x1, rooms[i].y1, rooms[i].y2, i, 1});
    }
    process_walls(walls);
    walls.clear();

    for (int i = 1; i <= n; i++) {
        walls.push_back({rooms[i].y2, rooms[i].x1, rooms[i].x2, i, 0});
        walls.push_back({rooms[i].y1, rooms[i].x1, rooms[i].x2, i, 1});
    }
    process_walls(walls);
    walls.clear();
    walls.shrink_to_fit();

    std::vector<Event> events;
    events.reserve(2 * n + m + 2);

    for (int i = 1; i <= n; i++) {
        events.push_back({rooms[i].x1, rooms[i].y1, rooms[i].y2, ROOM_START, i});
        events.push_back({rooms[i].x2, rooms[i].y1, rooms[i].y2, ROOM_END, i});
    }

    events.push_back({p.x, p.y, START_POINT, POINT, -1});
    events.push_back({s.x, s.y, END_POINT, POINT, -1});
    for (int i = 1; i <= m; i++) {
        Point a;
        std::cin >> a.x >> a.y;

        events.push_back({a.x, a.y, DANGER_POINT, POINT, -1});
    }

    std::sort(events.begin(), events.end());

    int start_idx = 0, end_idx = 0;

    std::set<Interval> active;
    for (const auto& e : events) {
        if (e.type == ROOM_END) {
            active.erase({e.y1, e.y2, e.id});
        } else if (e.type == ROOM_START) {
            active.insert({e.y1, e.y2, e.id});
        } else if (e.type == POINT) {
            auto it = active.upper_bound({e.y1, INF, -1});
            --it;

            int idx = (*it).id;
            if (e.y2 == START_POINT) {
                start_idx = idx;
            } else if (e.y2 == END_POINT) {
                end_idx = idx;
            } else {
                cannot[idx] = true;
            }
        }
    }

    events.clear();
    events.shrink_to_fit();
    active.clear();

    int ans = bfs(start_idx, end_idx) + 1;

    std::cout << ans << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}