Problem Description

Translated from JOI Open 2017 T3 "Golf"

In the first quadrant of the plane, there are $N$ rectangular obstacles. The pairs of opposite sides of each rectangle are parallel to the $x$-axis and $y$-axis, respectively. The bottom-left corner of rectangle $i (1 \le i \le N)$ is $(A_i, C_i)$, and the top-right corner is $(B_i, D_i)$. No two rectangles intersect, including at their boundaries.
JOI needs to hit a golf ball from $(S, T)$ to $(U, V)$, ensuring that these two points are different and that neither point is inside an obstacle or on its boundary.
JOI can only hit the ball in directions parallel to the $x$-axis or $y$-axis (JOI can move along with the ball). The ball can pass along the boundaries but cannot enter the interior of obstacles. The ball will stop when it hits an obstacle (JOI can still hit the ball in a direction away from the obstacle).
Determine the minimum number of hits required to get the golf ball to $(U, V)$.

Input Format

The first line contains four integers $S, T, U, V$.
The second line contains one integer $N$.
The next $N$ lines each contain four integers $A_i, B_i, C_i, D_i$.

Output Format

Output one line containing one integer, representing the minimum number of hits.

Sample Input and Output

Sample Input #1

3 5 8 6
1
5 6 2 8

Sample Output #1

3

Sample Input #2

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

Sample Output #2

1

Sample Input #3

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

Sample Output #3

4

Notes

Sample Explanation 1

$(3,5) \rightarrow (3,2) \rightarrow (8,2) \rightarrow (8,6)$

Data Range

$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) \neq (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.

见题面 Input 部分

见题面 Output 部分