개구리

덥고 건조한 여름, 배고픈 개구리 한 마리가 물과 먹이가 넉넉한 파리 나라로 향한다. 가는 길에 강을 건너야 한다. 평소라면 헤엄쳐 건너지만 지금은 너무 배고프고 지쳐서 걷기와 점프만 할 수 있다. 강 위에는 통나무가 떠 있고, 개구리는 통나무 위를 걸어 다니거나 한 통나무에서 다른 통나무로 점프할 수 있다.

걷는 데에는 에너지가 거의 들지 않으므로 걸은 거리는 따지지 않는다. 거리 $x$만큼 점프하면 에너지를 $x^2$만큼 쓴다. 한 번에 점프할 수 있는 거리는 최대 $\sqrt{l}$이다.

강과 양쪽 강가는 $n \times m$ 격자 위에 놓인다. $(a, b) - (c, d)$는 두 점 $(a, b)$와 $(c, d)$를 양 끝점으로 하는 선분이다. 아래쪽 강가와 위쪽 강가는 각각 꼭짓점을 차례로 이은 꺾은선이고, 통나무 하나는 선분 하나다. 모든 선분은 $x$축 또는 $y$축에 평행하다. 어떤 두 통나무도 공통 부분이 없고, 통나무와 강가도 공통 부분이 없다.

개구리는 같은 선분 위에서는 어느 위치로든 에너지를 쓰지 않고 움직일 수 있다. 강가는 꺾은선 전체가 이어져 있으므로 강가 위에서도 자유롭게 움직인다. 개구리는 아래쪽 강가에서 출발하고, 위쪽 강가에 닿는 순간 여행이 끝난다.

그림 1은 $8 \times 9$ 격자에 놓인 예다. 아래쪽 강가는 선분 7개, 위쪽 강가는 선분 11개로 이루어지고, 통나무는 차례로 $(0,3)-(2,3)$, $(4,2)-(6,2)$, $(3,5)-(6,5)$, $(7,4)-(7,6)$이다.

그림 1. 강 위의 통나무 네 개.

$l = 5$이면 통나무 1과 통나무 3을 차례로 밟고 건너가는 경로의 에너지가 $1^2 + (\sqrt{5})^2 + 1^2 = 7$이고, 이보다 적게 쓰는 방법은 없다. $l = 4$이면 강을 건널 수 없다.

개구리가 강을 건너는 데 필요한 에너지의 최솟값을 구하는 프로그램을 작성하시오.

첫 줄에 격자의 크기를 나타내는 두 정수 $n$과 $m$이 주어진다 ($3 \le n, m \le 5\,000$).

둘째 줄에 네 정수 $u$, $v$, $w$, $l$이 주어진다 ($2 \le u, v, w \le 2\max(n, m)$, $1 \le l \le \min((n-1)^2, (m-1)^2)$). 아래쪽 강가의 꼭짓점은 $u$개, 위쪽 강가의 꼭짓점은 $v$개이고, 강에는 통나무가 $w$개 떠 있다. 개구리가 한 번에 점프할 수 있는 최대 거리는 $\sqrt{l}$이다.

이어지는 $u$개의 줄에 아래쪽 강가의 꼭짓점 $(x, y)$가 한 줄에 하나씩 주어진다 ($0 \le x < n$, $0 \le y < m$). 꼭짓점은 시계 방향 순서이고, 가장 아래에 있으면서 가장 왼쪽인 꼭짓점이 맨 앞에 온다.

이어지는 $v$개의 줄에 위쪽 강가의 꼭짓점 $(x, y)$가 같은 형식으로 주어진다. 꼭짓점은 반시계 방향 순서이고, 가장 위에 있으면서 가장 왼쪽인 꼭짓점이 맨 앞에 온다.

강가에서 이웃한 두 꼭짓점을 이은 선분은 $x$축 또는 $y$축에 평행하다.

마지막 $w$개의 줄에 통나무 하나를 나타내는 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다 ($0 \le x_1, x_2 < n$, $0 \le y_1, y_2 < m$). 이 통나무는 선분 $(x_1, y_1) - (x_2, y_2)$이며, $x_1 = x_2$이거나 $y_1 = y_2$이다.

아래쪽 강가와 위쪽 강가는 만나지 않는다.

개구리가 강을 건너는 데 필요한 에너지의 최솟값을 한 줄에 출력한다. 개구리가 강을 건널 수 없으면 -1을 출력한다.