17172번 - Dijkstra Is Playing At My House 서브태스크다국어

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 better start moving.

New York City is modeled as a 2-dimensional plane. Dijkstra is now in coordinate $(s_x,\ s_y)$, and your house is located in coordinate $(e_x,\ e_y)$. Dijkstra should come to your house by only moving in a direction parallel to the coordinate axes (you remember the Manhattan distance, right?). Also, there are $N$ skyscraper in an axis-parallel rectangular shape, which you can pass through its boundary, but cannot pass through anywhere strictly inside of it.

You got a phone call from Dijkstra, saying that it's too hard for him to compute the shortest path between his location and your house. Somehow, he is losing his edge. However, that's not bad news, because it's a chance for you to be cool in front of the great Dijkstra. Can you?

It is guaranteed that all $x$ coordinates are distinct and all $y$ coordinates are distinct. It is also guaranteed that no pair of rectangles overlap. It is also guaranteed that your house and Dijkstra's starting location are not inside of any rectangles.

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

The $i$-th line of next $N$ lines contain four space-separated integers $a_i$, $b_i$, $c_i$, $d_i$. This indicates that $i$-th skyscraper is a rectangle with its four corners located in $(a_i,\ b_i),\ (a_i,\ d_i),\ (c_i,\ b_i),\ (c_i,\ d_i)$. 

Print the length of the shortest path between Dijkstra's location and your house, using the Manhattan metric.

• $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,\ a_2,\ \cdots,\ a_N,\ c_1,\ c_2,\ \cdots,\ c_N\}$, all elements in $X$ are distinct.

• Let $Y = \{s_y,\ e_y,\ b_1,\ b_2,\ \cdots,\ b_N,\ d_1,\ d_2,\ \cdots,\ d_N\}$, all elements in $Y$ are distinct.

• No pair of rectangles share a common point.

• Dijkstra's location and your house's location are not in any of the rectangles.

This subtask has an additional constraint. 

• $N \le {\color{red}{500}}$

This subtask has an additional constraint. 

• $N \le 5\,000$

This subtask has no additional constraints.