Mechi was gifted a goat. To prevent the goat from damaging her garden, she decided to protect the crops with a wooden fence in the shape of a convex polygon. The fence has a post at each vertex of the polygon, and Mechi's idea is to tie the goat with a rope to one of these posts, so that it can eat the grass outside the fence. The grazing region will be determined by the portion of the land that the goat can access without either it or the rope crossing the fence at any time.
In the following figure, a rectangular fence is shown with the goat tied to the upper left post. The grazing region appears in gray.
Mechi has not yet decided which rope to buy. She has been offered several ropes of certain lengths and wants to know, for each of them, the area of the goat's grazing region.
Note: sometimes using acos to calculate angles can cause a large precision error. The recommended function for that is atan2.
The first line contains two integers $$$N$$$ ($$$3 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), which indicate respectively the number of vertices of the polygonal fence protecting the garden, and the number of ropes offered to Mechi.
Each of the following $$$N$$$ lines contains two integers $$$X$$$ and $$$Y$$$ ($$$-10^8 \leq X, Y \leq 10^8$$$), indicating that the fence has a vertex with coordinates $$$(X,Y)$$$. The vertices describe a simple convex polygon that does not have three collinear vertices, and they appear in the input in counterclockwise order, starting from the vertex where Mechi will tie the goat.
The next line contains $$$Q$$$ integers $$${L_1}, {L_2}, \ldots, {L_Q}$$$ ($$$1 \leq L_i \leq 10^8$$$), indicating the lengths of the ropes offered.
Write $$$Q$$$ lines. The $$$i$$$-th line must contain a number $$$R_i$$$ equal to the area that the goat could reach if it were tied with a rope of length $$$L_i$$$.
Each value $$$R_i$$$ will be considered correct if it has a relative or absolute error less than or equal to $$$10^{-6}$$$. Formally, if $$$J_i$$$ is the jury's answer for a rope of length $$$L_i$$$, then the answer $$$R_i$$$ will be accepted if and only if $$$\frac{|R_i - J_i|}{\max{(1, |J_i|)}} \le 10^{-6}$$$.
4 1 0 2 0 0 3 0 3 2 4
41.626102660065
3 5 0 0 2 0 0 1 1 2 1 3 4
2.356194490192 10.441999928667 2.356194490192 26.132741228718 48.020700514225
The first example appears in the figure of the statement. The only rope offered has a length of $$$4$$$, and the corresponding grazing area is shown in gray. We can see that for the goat to access certain portions of the land, the rope must go around the fence, as neither it nor the goat can cross it.
