405991: GYM102202 I 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 5 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 integers $$$N, s_x, s_y, e_x, e_y$$$. ($$$1 \le N \le 250 000, 0 \le s_x, s_y, e_x, e_y \le 10^8$$$)

The next $$$N$$$ lines contain four 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)$$$. ($$$0 \le a_i < c_i \le 10^8$$$, $$$0 \le b_i < d_i \le 10^8$$$).

It is guaranteed that:

• Let $$$X = \{s_x, e_x, a_1, a_2, \cdots, a_N, c_1, c_2, \cdots, c_N\}, Y = \{s_y, e_y, b_1, b_2, \cdots, b_N, d_1, d_2, \cdots, d_N\}$$$. All elements in $$$X$$$ are distinct, and 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.

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

3 2 14 5 1
4 6 6 10
0 7 3 9
1 2 8 5

20

1 0 500 100 503
1 0 99 1000

1097

2 2 8 10 3
3 6 6 10
7 1 8 7

15