다익스트라가 우리 집에서 놀고 있다

시간 제한3초메모리 제한1024 MB

요약

서로 겹치지 않는 축 평행 직사각형 최대 25만 개를 피해 시작점에서 집까지 가는 최단 맨해튼 거리를 구합니다.

난이도: 어려움10점 중 9점
유형: 최단 경로, 세그먼트 트리, 정렬, 기하
정답자: 아직 제출이 없습니다

문제

ICPC 월드 파이널 우승을 축하하기 위해 다익스트라(Edsger W. Dijkstra, 다익스트라 알고리즘을 만든 사람이자 알고리즘 이름의 주인공)가 뉴욕에 있는 당신의 집에서 성대한 파티를 연다. 파티는 4시간 뒤에 시작하니 그는 지금 출발하는 편이 좋다.

뉴욕은 2차원 평면으로 모델링된다. 다익스트라는 좌표 $(s_x, s_y)$ 에 있고, 당신의 집은 $(e_x, e_y)$ 에 있다. 그는 좌표축에 평행한 방향으로만 이동할 수 있다(맨해튼 거리를 기억하고 있겠지?). 축에 평행한 직사각형 모양의 고층 빌딩이 $N$ 개 있다. 빌딩의 경계는 통과할 수 있지만, 빌딩 내부의 점은 통과할 수 없다.

다익스트라에게서 전화가 왔다. 그의 현재 위치에서 당신의 집까지 최단 경로를 계산하는 것이 자신에게는 너무 어렵다고 한다. 감이 조금 떨어진 모양이다. 그래도 나쁜 소식만은 아니다. 위대한 다익스트라 앞에서 실력을 보여줄 기회이기 때문이다. 해낼 수 있겠는가?

모든 x 좌표는 서로 다르고, 모든 y 좌표도 서로 다르다. 어떤 두 직사각형도 겹치지 않는다. 당신의 집과 다익스트라의 출발 위치는 어떤 직사각형 내부에도 있지 않다.

입력

첫째 줄에 다섯 정수 $N$ , $s_x$ , $s_y$ , $e_x$ , $e_y$ 가 공백으로 구분되어 주어진다.

다음 $N$ 개 줄의 $i$ 번째 줄에는 네 정수 $a_i$ , $b_i$ , $c_i$ , $d_i$ 가 공백으로 구분되어 주어진다. 이는 $i$ 번째 고층 빌딩이 네 꼭짓점 $(a_i, b_i)$ , $(a_i, d_i)$ , $(c_i, b_i)$ , $(c_i, d_i)$ 를 갖는 직사각형이라는 뜻이다.

출력

다익스트라의 위치에서 당신의 집까지 최단 경로의 길이를 맨해튼 거리로 계산해 출력한다.

제한

$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$ )
$X = \{s_x, e_x, a_1, \ldots, a_N, c_1, \ldots, c_N\}$ 라 하면, $X$ 의 모든 원소는 서로 다르다.
$Y = \{s_y, e_y, b_1, \ldots, b_N, d_1, \ldots, d_N\}$ 라 하면, $Y$ 의 모든 원소는 서로 다르다.
어떤 두 직사각형도 공통된 점을 갖지 않는다.
다익스트라의 위치와 당신의 집은 어떤 직사각형에도 속하지 않는다.

예제3

예제 1
입력
```
3 2 14 5 1
4 6 6 10
0 7 3 9
1 2 8 5
```
예상 출력
```
20
```
예제 2
입력
```
1 0 500 100 503
1 0 99 1000
```
예상 출력
```
1097
```
예제 3
입력
```
2 2 8 10 3
3 6 6 10
7 1 8 7
```
예상 출력
```
15
```