H. SDUcell
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For mobile operators, it is extremely important to place radio towers as close to users as possible, as the distance between the tower and the user directly affects the signal strength. The further the user is from the tower, the weaker the signal will be, which can lead to call drops, low data transfer speeds, and overall low mobile network performance. By placing radio towers closer to users, mobile operators can guarantee that users will receive a strong and stable signal, which is necessary for providing high-quality mobile services and maintaining customer satisfaction.

A very well-known mobile operator, SDUcell, has $$$n$$$ radio towers in the city. In this problem, the city can be represented as a two-dimensional Euclidean plane and the $$$i$$$-th radio tower is located at the integer coordinate $$$(x_i, y_i)$$$. The distance between two points is measured by the Euclidean distance, which is the length of the shortest line segment connecting the given points.

An active user of this operator, Marco, decided to take a walk through the streets of the city and chat with friends during the walk. He has already determined his route and highlighted $$$m$$$ points on the map.

He starts his route at point $$$(a_1, b_1)$$$. Then he will walk in a straight line to point $$$(a_2, b_2)$$$, from there to point $$$(a_3, b_3)$$$ and so on. In the end, he will finish his route at point $$$(a_m, b_m)$$$.

The peculiarity of his route is that the streets in the city are arranged in a rectangular shape. Since Marco always walks along the streets, each part of his route will be either strictly horizontal or strictly vertical. More formally, for all $$$1 \le i \le m-1$$$, either $$$a_i = a_{i+1}$$$ or $$$b_i = b_{i+1}$$$ will always hold.

Marco moves at a constant speed of one unit per second. That is, the distance traveled is directly proportional to the time spent, and Marco will cover $$$d$$$ units of distance in $$$d$$$ seconds.

At each moment in time, the mobile operator SDUcell will connect Marco's phone to the nearest radio tower. At the end of the route, SDUcell calculates the cost of the call in a very interesting way:

  • Let's denote the total travel time of Marco as $$$d$$$. We will assume that Marco started the call at time $$$0$$$ and ended it at time $$$d$$$. For each moment in time $$$t$$$ ($$$0 \le t \le d$$$), we define the value $$$f(t)$$$ as the distance from Marco to the nearest radio tower at that moment.
  • Then, the cost of the call in tenge will be determined as the area under the function $$$C(t) = f(t)^2$$$ in the interval $$$[0, d]$$$.

How much will Marco have to pay?

Input

The first line of the input file contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of radio towers of the mobile operator SDUcell.

The next $$$n$$$ lines contain the integer coordinates of the radio towers $$$(x_i, y_i)$$$ ($$$-1000 \le x_i, y_i \le 1000$$$). It is guaranteed that all coordinates are distinct.

The next line contains a single integer $$$m$$$ ($$$1 \le m \le 500$$$) — the number of points in Marco's route.

The next $$$m$$$ lines contain the integer coordinates of all the points in Marco's route $$$(a_i, b_i)$$$ ($$$-1000 \le a_i, b_i \le 1000$$$). It is guaranteed that all points on the route are distinct. It is also guaranteed that for all $$$1 \le i \le m-1$$$, either $$$a_i = a_{i+1}$$$ or $$$b_i = b_{i+1}$$$ holds.

Output

Output a single real number — the sum that Marco will have to pay. Your answer will be considered correct if its relative or absolute error does not exceed $$$10^{-6}$$$.

Examples
Input
2
1 0
0 -2
4
0 0
0 -1
1 -1
1 -2
Output
3.500000000
Input
3
0 0
2 2
0 9
2
0 0
0 9
Output
44.678571429
Note

Here is a visualization of the first example.

Marco's route, locations of radio towers, and the function $$$C(t)$$$