Little Z has been fond of mathematics since he was a child. The clever boy particularly enjoys studying small mathematical problems.

One day, Little Z chose $n$ points on a piece of paper and connected them pairwise with a pencil, forming $n(n-1)/2$ line segments. Since the pencil is very thin, the width of these line segments can be considered to be 0.

Looking at these line segments, Little Z fell into deep thought. He believed that some of these line segments were more important and needed to be highlighted. Therefore, Little Z took out a brush and traced over them. The brush, when applied to the paper, forms a circle with radius $r$. When tracing a line segment, the center of the brush (i.e., the center of the circle) starts from one endpoint of the segment and moves along the segment to the other endpoint. The figure below shows a graph with 4 points, where one of the line segments has been highlighted by tracing.

Now, Little Z is very curious about the total area of the region on the paper that is highlighted after the tracing. Can you help him solve this problem?

Input

This is an answer-submission problem. All input files path1.in through path10.in are already provided in the corresponding directory.

The first line of the input file path*.in contains a positive integer $n$, representing the number of chosen points.

The 2nd to $(n+1)$-th lines each contain two real numbers $x_i, y_i$, representing the coordinates of point $i$ as $(x_i, y_i)$.

The $(n+2)$-th line contains a positive integer $m$, representing the number of line segments that Little Z considers important.

The $(n+3)$-th to $(n+m+2)$-th lines each contain two positive integers $a, b$, representing a line segment. The two numbers $a$ and $b$ represent the indices of the two endpoints of the segment.

The $(n+m+3)$-th line contains a real number $r$, representing the radius of the circle formed by the brush on the paper.

The $(n+m+4)$-th line contains four real numbers $p_1, p_2, p_3, p_4$, which are parameters used for scoring.

Output

The output file path*.out contains only one line, which is the total area of the highlighted region after tracing.

Examples

Input 1

2
1 1
1 2
1
1 2
1
0.00001 0.001 0.1 1

Output 1

5.1415927

Note

As shown in the figure below.

Subtasks

Each test case is scored individually.

This problem has 4 scoring parameters $p_1, p_2, p_3, p_4$ ($p_1 < p_2 < p_3 < p_4$), which are given in the input file.

Your score will be determined according to the following rules: If the difference between your answer and the standard answer is no more than $p_1$, you will receive full marks for this test case. Otherwise, if the difference between your answer and the standard answer is no more than $p_2$, you will receive 70% of the marks for this test case. Otherwise, if the difference between your answer and the standard answer is no more than $p_3$, you will receive 40% of the marks for this test case. Otherwise, if the difference between your answer and the standard answer is no more than $p_4$, you will receive 10% of the marks for this test case. * Otherwise, your score for this test case will be 0.