Frog

In a hot, dry summer a hungry frog travels toward the land of flies, where water and food are plentiful. On the way it has to cross a river. The frog normally swims, but right now it is so hungry and tired that it can only walk and jump. Logs float on the river, and the frog can walk along a log or jump from one log to another.

Walking costs almost no energy, so the distance walked does not count. A jump of distance $x$ costs $x^2$ energy. The frog can jump a distance of at most $\sqrt{l}$ at a time.

The river and both banks lie on an $n \times m$ grid. $(a, b) - (c, d)$ is the segment whose endpoints are $(a, b)$ and $(c, d)$. Each bank is a polyline through its vertices in the given order, and each log is a single segment. Every segment is parallel to the $x$ axis or to the $y$ axis. No two logs share a common part, and no log shares a common part with a bank.

The frog moves to any position on the same segment without spending energy. A bank is one connected polyline, so the frog also moves freely along a whole bank. The frog starts on the lower bank, and the trip ends the moment it reaches the upper bank.

Figure 1 shows an example on an $8 \times 9$ grid. The lower bank consists of 7 segments, the upper bank consists of 11 segments, and the logs are $(0,3)-(2,3)$, $(4,2)-(6,2)$, $(3,5)-(6,5)$, $(7,4)-(7,6)$ in that order.

Figure 1. Four logs on the river.

With $l = 5$, stepping on log 1 and then on log 3 costs $1^2 + (\sqrt{5})^2 + 1^2 = 7$ energy, and no route costs less. With $l = 4$ the frog cannot cross the river.

Write a program that computes the minimum energy the frog needs to cross the river.

The first line has two integers $n$ and $m$, the size of the grid ($3 \le n, m \le 5\,000$).

The second line has four integers $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)$). The lower bank has $u$ vertices, the upper bank has $v$ vertices, and $w$ logs float on the river. The frog jumps a distance of at most $\sqrt{l}$ at a time.

Each of the next $u$ lines has two integers $x$ and $y$ ($0 \le x < n$, $0 \le y < m$), one vertex $(x, y)$ of the lower bank. The vertices come in clockwise order, and the bottommost vertex, leftmost among those, comes first.

Each of the next $v$ lines has two integers $x$ and $y$ in the same format, one vertex of the upper bank. The vertices come in counterclockwise order, and the topmost vertex, leftmost among those, comes first.

On a bank, the segment joining two neighboring vertices is parallel to the $x$ axis or to the $y$ axis.

Each of the last $w$ lines has four integers $x_1$, $y_1$, $x_2$, $y_2$ ($0 \le x_1, x_2 < n$, $0 \le y_1, y_2 < m$) describing one log, the segment $(x_1, y_1) - (x_2, y_2)$. Either $x_1 = x_2$ or $y_1 = y_2$ holds.

The lower bank and the upper bank do not meet.

Print on one line the minimum energy the frog needs to cross the river. If the frog cannot cross the river, print -1.