Golf

Time limit5sMemory limit1024 MB

Summary

Find the fewest axis-parallel hits needed to move a golf ball from (S, T) to (U, V) without passing through any rectangular obstacle interior.

Level: Medium7 of 10
Topics: BFS, Graph, Segment tree
Solved: No attempts yet

Problem

JOI-kun is a boy practicing golf on a special golf course.

The course is a plane with $xy$ -coordinates. It contains $N$ obstacles. The $i$ -th obstacle ( $1 \le i \le N$ ) occupies the rectangular region whose $x$ -coordinates are between $A_i$ and $B_i$ (inclusive) and whose $y$ -coordinates are between $C_i$ and $D_i$ (inclusive). Two obstacles, including their boundaries, do not intersect.

The start point is $(S, T)$ and the end point is $(U, V)$ . The two points are different, and neither is contained in any obstacle or on any obstacle boundary. At the beginning, the golf ball is placed at the start point.

JOI-kun hits the ball and moves it any distance in one of the four directions parallel to the coordinate axes. The track of the ball must not touch the interior of any obstacle. The ball may pass through obstacle boundaries, and it may stop on a boundary. From a stopped position, the ball can be hit in any direction that has no obstacle immediately blocking it.

Find the minimum number of hits needed to move the ball from the start point to the end point.

Input

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

Output

Print the minimum number of hits on one line.

Constraints

$1 \le S, T, U, V \le 1\,000\,000\,000$
$1 \le N \le 100\,000$
$1 \le A_i < B_i \le 1\,000\,000\,000$ for every $i$
$1 \le C_i < D_i \le 1\,000\,000\,000$ for every $i$
$(S, T) \ne (U, V)$
Obstacles do not intersect each other, including their boundaries.
The start and end points are not contained in any obstacle or on any obstacle boundary.

Examples3

Example 1
Input
```
3 5 8 6
1
5 6 2 8
```
Expected output
```
3
```
Example 2
Input
```
1 1 1 10
3
5 6 2 8
1 2 2 3
8 10 3 5
```
Expected output
```
1
```

Example 3

Input

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

Expected output