Problem Description

Translated from JOI Open 2017 T3 “ゴルフ / Golf”.

There are $N$ rectangular obstacles in the first quadrant of the plane. For each rectangle, its two pairs of opposite sides are parallel to the $x$-axis and the $y$-axis, respectively. The lower-left corner of rectangle $i(1\le i\le N)$ is $(A_i, C_i)$, and the upper-right corner is $(B_i, D_i)$. Any two rectangles (including their boundaries) do not intersect.
JOI needs to hit a golf ball from $(S,T)$ to $(U,V)$. It is guaranteed that these two points are different, and that neither point lies inside any obstacle nor on the boundary of any obstacle.
JOI can only hit the ball in a direction parallel to the $x$-axis or parallel to the $y$-axis (JOI can move along with it). The ball may pass along boundaries, but it cannot enter the interior of any obstacle. If the ball hits an obstacle, it stops (JOI can still hit it in a direction away from the obstacle).
Find the minimum number of hits needed to get the golf ball into $(U,V)$.

Input Format

The first line contains four integers $S, T, U, V$.
The second line contains an integer $N$.
Each of the next $N$ lines contains four integers $A_i, B_i, C_i, D_i$.

Output Format

Output one line with one integer, the minimum number of hits.

3 5 8 6
1
5 6 2 8

3

1 1 1 10
3
5 6 2 8
1 2 2 3
8 10 3 5

1

20 68 85 74
5
30 70 14 100
5 24 15 67
75 86 75 79
75 90 19 62
93 98 26 58

4

Hint

Sample Explanation 1

$(3,5) → (3,2) → (8,2) → (8,6)$

Constraints

$1\le S, T, U, V\le 10^9, 1\le N\le 10^5, 1\le A_i<B_i\le 10^9, 1\le C_i<D_i\le 10^9,$ $(S,T)≠(U,V)$。

• Subtask #1 (10 points): $S, T, U, V, N, B_i, D_i\le 1000$；
• Subtask #2 (20 points): $N\le 1000$；
• Subtask #3 (70 points): No additional constraints.

Translated by ChatGPT 5