Road

Time limit1sMemory limit1024 MB

Summary

Find the shortest path from A to B along the edges of N axis-aligned rectangles.

Level: Medium7 of 10
Topics: Graph, Shortest path, Geometry, Sorting
Solved: No attempts yet

Problem

An island is divided into $N$ plots of land, and each plot is an axis-aligned rectangle. A road must be built from point $A$ to point $B$ . Because no landowner wants the road to split their plot into several smaller pieces, the road may run only along the plot boundaries (the edges of the rectangles).

Write a program that finds the length of the shortest such road from point $A$ to point $B$ .

Input

The first line contains the number of plots $N$ ( $1 \le N \le 1000$ ). Each of the next $N$ lines contains the coordinates $X_0$ , $Y_0$ , $X_1$ , $Y_1$ of the bottom-left and top-right corners of the rectangle that describes one plot. The next line contains the coordinates $X_A$ , $Y_A$ of point $A$ , and the last line contains the coordinates $X_B$ , $Y_B$ of point $B$ .

All coordinates are non-negative integers not exceeding $1\,000\,000$ . Points $A$ and $B$ always lie on the boundary of some plot. All plots together form a single island (which may contain lakes), and a road from $A$ to $B$ is guaranteed to exist.

Output

Output a single integer $L$ — the length of the shortest road from point $A$ to point $B$ . Because all coordinates are integers and the road follows only axis-aligned segments, $L$ is always an integer.

Examples3

Example 1
Input
```
3
4 1 7 4
3 4 6 5
1 3 4 4
4 5
3 3
```
Expected output
```
5
```
Example 2
Input
```
1
0 0 2 2
0 0
2 0
```
Expected output
```
2
```
Example 3
Input
```
1
0 0 3 4
0 0
3 4
```
Expected output
```
7
```