MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

There is a city whose shape is a $1{,}000 \\times 1{,}000$ square. The city has a big river, which flows from the north to the south and separates the city into just two parts: the west and the east.

Recently, the city mayor has decided to build a highway from a point $s$ on the west part to a point $t$ on the east part. A highway consists of a bridge on the river, and two roads: one of the roads connects $s$ and the west end of the bridge, and the other one connects $t$ and the east end of the bridge. Note that each road doesn’t have to be a straight line, but the intersection length with the river must be zero.

In order to cut building costs, the mayor intends to build a highway satisfying the following conditions:

• Since bridge will cost more than roads, at first the length of a bridge connecting the east part and the west part must be as short as possible.
• Under the above condition, the sum of the length of two roads is minimum.

Your task is to write a program computing the total length of a highway satisfying the above conditions.

Input

The input consists of a single test case. The test case is formatted as follows.

$sx$ $sy$ $tx$ $ty$
$N$
$wx\_1$ $wy\_1$
:
:
$wx\_N$ $wy\_N$
$M$
$ex\_1$ $ey\_1$
:
:
$ex\_M$ $ey\_M$

At first, we refer to a point on the city by a coordinate $(x, y)$: the distance from the west side is $x$ and the distance from the north side is $y$.

The first line contains four integers $sx$, $sy$, $tx$, and $ty$ ($0 \\leq sx, sy, tx, ty \\leq 1{,}000$): points $s$ and $t$ are located at $(sx, sy)$ and $(tx, ty)$ respectively. The next line contains an integer $N$ ($2 \\leq N \\leq 20$), where $N$ is the number of points composing the west riverside. Each of the following $N$ lines contains two integers $wx\_i$ and $wy\_i$ ($0 \\leq wx\_i, wy\_i \\leq 1{,}000$): the coordinate of the $i$-th point of the west riverside is $(wx\_i, wy\_i)$. The west riverside is a polygonal line obtained by connecting the segments between $(wx\_i, wy\_i)$ and $(wx\_{i+1}, wy\_{i+1})$ for all $1 \\leq i \\leq N-1$. The next line contains an integer $M$ ($2 \\leq M \\leq 20$), where $M$ is the number of points composing the east riverside. Each of the following $M$ lines contains two integers $ex\_i$ and $ey\_i$ ($0 \\leq ex\_i, ey\_i \\leq 1{,}000$): the coordinate of the $i$-th point of the east riverside is $(ex\_i, ey\_i)$. The east riverside is a polygonal line obtained by connecting the segments between $(ex\_i, ey\_i)$ and $(ex\_{i+1}, ey\_{i+1})$ for all $1 \\leq i \\leq M-1$.

You can assume that test cases are under the following conditions.

• $wy\_1$ and $ey\_1$ must be 0, and $wy\_N$ and $ey\_M$ must be $1{,}000$.
• Each polygonal line has no self-intersection.
• Two polygonal lines representing the west and the east riverside have no cross point.
• A point $s$ must be on the west part of the city. More precisely, $s$ must be on the region surrounded by the square side of the city and the polygonal line of the west riverside and not containing the east riverside points.
• A point $t$ must be on the east part of the city. More precisely, $t$ must be on the region surrounded by the square side of the city and the polygonal line of the east riverside and not containing the west riverside points.
• Each polygonal line intersects with the square only at the two end points. In other words, $0 < wx\_i, wy\_i <1{,}000$ holds for $2 \\leq i \\leq N-1$ and $0 < ex\_i, ey\_i <1{,}000$ holds for $2 \\leq i \\leq M-1$.

Output

Output single-space separated two numbers in a line: the length of a bridge and the total length of a highway (i.e. a bridge and two roads) satisfying the above mayor's demand. The output can contain an absolute or a relative error no more than $10^{-8}$.

Sample Input 1

200 500 800 500
3
400 0
450 500
400 1000
3
600 0
550 500
600 1000```

### Output for the Sample Input 1

```plain
100 600```

* * *

### Sample Input 2

```plain
300 300 700 100
5
300 0
400 100
300 200
400 300
400 1000
4
700 0
600 100
700 200
700 1000```

### Output for the Sample Input 2

```plain
200 541.421356237```

* * *

### Sample Input 3

```plain
300 400 700 600
2
400 0
400 1000
2
600 0
600 1000```

### Output for the Sample Input 3

```plain
200 482.842712475```

* * *

### Sample Input 4

```plain
200 500 800 500
3
400 0
450 500
400 1000
5
600 0
550 500
600 100
650 500
600 1000```

### Output for the Sample Input 4

```plain
100 1200.326482915```

* * *