Minimum Cost Defense Fence

A country A is preparing to build a long defensive fence inside its territory in order to protect its cities. The geography of country A is special: the x-axis represents a river that naturally acts as a defense so you do not need to build a fence along it.

You are given the coordinates of all cities of country A. There are always two cities on the river: one at \( (0,0) \) and one at \( (n,0) \) (where \( n \) is determined by the x-coordinate of the river city other than \( (0,0) \)). All other cities have their x-coordinates strictly between 0 and \( n \) and y-coordinate greater than 0. Moreover, there is one capital (which is not \( (0,0) \) or \( (n,0) \)) that must always be protected. In addition, the two river cities are compulsory and must be protected.

Due to economic constraints, the decision makers have decided that in each query they will cancel the protection for one city (except the compulsory ones). For each query you are to determine the minimum total cost to build the defense fence that encloses all protected cities.

The fence is built along the upper convex hull of the protected cities. In other words, if the points on the upper convex hull are \( P_1,P_2,\dots,P_k \) (with \( P_1=(0,0) \) and \( P_k=(n,0) \)), then the cost is given by

\[ \text{Cost} = \sum_{i=1}^{k-1} \sqrt{(P_{i+1,x}-P_{i,x})^2+(P_{i+1,y}-P_{i,y})^2}. \]

Note that the query cancelling protection for a city does not affect the compulsory cities (\( (0,0) \), \( (n,0) \), and the capital) even if such a query is issued. Each query is independent (i.e. the canceled protection applies only for that query).

inputFormat

The input begins with a line containing two integers \( m \) and \( q \), representing the total number of cities and the number of queries, respectively.

The second line contains one integer \( c \) (1-indexed), representing the index of the capital city. The capital is guaranteed not to be at \( (0,0) \) or \( (n,0) \).

Then follow \( m \) lines. Each of these lines contains two integers \( x \) and \( y \) representing the coordinates of a city. It is guaranteed that exactly two cities lie on the river: one at \( (0,0) \) and one at \( (n,0) \). The remaining cities have \( x \) strictly between 0 and \( n \) and \( y > 0 \).

Finally, there are \( q \) lines, each containing an integer \( u \) (1-indexed), which specifies the city whose protection is revoked in that query. If \( u \) corresponds to a compulsory city (i.e. one of \( (0,0) \), \( (n,0) \), or the capital), then the removal is ignored.

outputFormat

For each query, output one line containing the minimum total cost to build the defense fence, with a precision of 6 decimal places. The cost is the sum of the Euclidean distances between consecutive points on the upper convex hull of all protected cities.

sample

5 3
3
0 0
4 0
2 2
1 1
3 1
4
5
3

5.656854
5.656854
5.656854