Maximal polygon brightness

Problem

A convex polygon $P$ lies in the plane. Put a light source at a point $T$ outside $P$ , and some edges of $P$ become lit. If $A$ and $B$ are two consecutive vertices of $P$ , the edge $AB$ is lit when the area of triangle $TAB$ is not zero and that triangle does not meet the interior of $P$ .

The brightness of the polygon is the sum of the lengths of the lit edges. The maximal brightness is the largest brightness you can reach by choosing the best point $T$ . The distance between $T$ and the polygon is unrestricted, and the coordinates of $T$ do not have to be integers.

The polygons $P$ , $P_1$ , $P_2$ and $P_3$ from the second example. The figure also marks the maximal brightness.

The vertices of $P$ are, in order, $A_1, A_2, \dots, A_n$ . The polygon changes over $q$ steps. In step $j$ you delete one vertex that is still present and obtain a new polygon $P_j$ . The vertices of $P_j$ are the vertices of $P$ that have not been deleted, in the order they had in $P$ . Every $P_j$ is convex as well.

Compute the maximal brightness of $P$ and of each polygon $P_1, P_2, \dots, P_q$ .

Input

The first line contains the number of vertices $n$ of the initial polygon $P$ .

The $j$ -th of the next $n$ lines contains two integers $x_j$ and $y_j$ , the coordinates of vertex $A_j$ ( $-10^9 \le x_j, y_j \le 10^9$ ).

The next line contains the number of steps $q$ ( $0 \le q \le n - 3$ ).

The $j$ -th of the next $q$ lines contains an integer $k_j$ ( $1 \le k_j \le n$ ), meaning that step $j$ deletes vertex $A_{k_j}$ .

The vertices of $P$ are given counter-clockwise, no two consecutive edges are parallel, and all $k_j$ are distinct.

Output

Print $q + 1$ lines.

The first line holds the maximal brightness of the initial polygon $P$ . The $j$ -th of the next $q$ lines holds the maximal brightness of the polygon $P_j$ obtained after step $j$ .

Round every value to six decimal places and print all six digits, trailing zeros included. In every test the answer stays far from a rounding boundary, so double precision arithmetic prints the same digits.