Dijkstra Is Playing At My House

Time limit3sMemory limit1024 MB

Summary

Find the shortest Manhattan path from start to house around up to 250,000 non-overlapping axis-parallel rectangles, without entering any rectangle interior.

Level: Hard9 of 10
Topics: Shortest path, Segment tree, Sorting, Geometry
Solved: No attempts yet

Problem

To celebrate your team's victory at ICPC World Finals, Edsger W. Dijkstra (the inventor and namesake of Dijkstra's algorithm) will throw a fabulous party at your house in New York City. The party starts in 4 hours, so he should start moving soon.

New York City is modeled as a 2-dimensional plane. Dijkstra is at coordinate $(s_x, s_y)$ , and your house is at $(e_x, e_y)$ . He can only move in directions parallel to the coordinate axes (you remember the Manhattan distance, right?). There are $N$ skyscrapers, each an axis-parallel rectangle. He may pass through a skyscraper's boundary, but he cannot pass through any point strictly inside one.

Dijkstra called you because computing the shortest path between his location and your house is too hard for him. He seems to be losing his edge. That is not bad news. It is your chance to impress the great Dijkstra. Can you?

All x coordinates are distinct, and all y coordinates are distinct. No pair of rectangles overlaps. Your house and Dijkstra's starting location are not inside any rectangle.

Input

The first line contains five space-separated integers $N$ , $s_x$ , $s_y$ , $e_x$ , $e_y$ .

The $i$ -th of the next $N$ lines contains four space-separated integers $a_i$ , $b_i$ , $c_i$ , $d_i$ . This means the $i$ -th skyscraper is a rectangle with corners at $(a_i, b_i)$ , $(a_i, d_i)$ , $(c_i, b_i)$ , and $(c_i, d_i)$ .

Output

Print the length of the shortest path between Dijkstra's location and your house, measured in Manhattan distance.

Constraints

$1 \le N \le 250\,000$
$0 \le s_x, s_y, e_x, e_y \le 10^8$
$0 \le a_i < c_i \le 10^8$ ( $1 \le i \le N$ )
$0 \le b_i < d_i \le 10^8$ ( $1 \le i \le N$ )
Let $X = \{s_x, e_x, a_1, \ldots, a_N, c_1, \ldots, c_N\}$ . All elements in $X$ are distinct.
Let $Y = \{s_y, e_y, b_1, \ldots, b_N, d_1, \ldots, d_N\}$ . All elements in $Y$ are distinct.
No pair of rectangles shares a common point.
Dijkstra's location and your house are not in any rectangle.

Examples3

Example 1
Input
```
3 2 14 5 1
4 6 6 10
0 7 3 9
1 2 8 5
```
Expected output
```
20
```
Example 2
Input
```
1 0 500 100 503
1 0 99 1000
```
Expected output
```
1097
```
Example 3
Input
```
2 2 8 10 3
3 6 6 10
7 1 8 7
```
Expected output
```
15
```