가장 긴 최단 경로

평면 위에 축에 평행한 직사각형 $n$개와 수직 선분 $S$, $T$가 있다. 직사각형과 선분의 모든 꼭짓점은 정수 좌표에 있다. 직사각형과 선분은 서로 떨어져 있어서, 두 도형이 교차하지도 않고 경계 점을 공유하지도 않는다. 선분 $S$ 위의 점 $p$와 선분 $T$ 위의 점 $q$에 대해, $p$와 $q$를 잇는 경로는 수평 또는 수직 선분들을 이은 연결선이며, 직사각형의 내부와 교차하지 않는다. 경로의 길이는 그 경로를 이루는 선분 길이의 합이다. $p$와 $q$ 사이의 최단 경로는 $p$와 $q$ 사이의 모든 경로 중 길이가 가장 짧은 경로이다.

$S$ 위의 점과 $T$ 위의 점에 대해, 두 점을 잇는 최단 경로는 항상 존재한다. $d(p, q)$는 $S$ 위의 점 $p$와 $T$ 위의 점 $q$를 잇는 최단 경로의 길이를 뜻한다. 구하려는 값은 $S$ 위의 점과 $T$ 위의 점을 잇는 최단 경로들 중 가장 긴 경로의 길이, 즉 $\displaystyle\max\_{p ∈ S}\max\_{q ∈ T}d(p,q)$이다.

(a)	(b)

그림 (a)에는 선분 $S$와 $T$만 있고 직사각형은 없다. $S$ 위의 점과 $T$ 위의 점을 잇는 최단 경로는 모두 길이가 $9$ 이하이고, $d(s, t) = 9$이다. 따라서 답은 $9$이다. 그림 (b)에는 직사각형 $A$와 선분 $S$, $T$가 있다. $S$ 위의 점 $s$와 $T$ 위의 점 $t$ 사이에는 빨간색과 파란색 두 개의 최단 경로가 있다. 여기서 $d(s, t) = 11$이고, $S$ 위의 점과 $T$ 위의 점을 잇는 최단 경로의 길이는 모두 $11$ 이하이다. 답은 $11$이다.

첫 줄에는 여섯 개의 정수가 주어진다. 처음 세 정수는 선분 $S$의 $x$좌표와 두 $y$좌표이고, 나머지 세 정수는 선분 $T$의 $x$좌표와 두 $y$좌표이다.

다음 줄에는 직사각형의 개수 $n$ ($0 \le n \le 5\,000$)이 주어진다. 직사각형에는 $1$번부터 $n$번까지 번호가 매겨진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 직사각형 $i$의 왼쪽 위 꼭짓점의 $x$좌표와 $y$좌표, 오른쪽 아래 꼭짓점의 $x$좌표와 $y$좌표를 나타내는 음이 아닌 정수 네 개가 주어진다.

선분 $S$, $T$의 끝점 좌표와 직사각형의 꼭짓점 좌표는 모두 $10^8$ 이하의 음이 아닌 정수이다.

$S$ 위의 점과 $T$ 위의 점을 잇는 모든 최단 경로 중 가장 긴 경로의 길이를 한 줄에 출력한다.

예제 입력 1은 그림 (a)의 경우에, 예제 입력 2는 그림 (b)의 경우에 해당한다.