Rolling the Bottle

Jonghun has a water bottle shaped like a right prism whose base is a convex polygon. A little water is inside.

Jonghun laid the bottle down completely, so every edge that does not belong to the two bases is parallel to the floor. When he rolls the bottle in this position, the base polygon turns through every angle inside a plane perpendicular to the floor. The water returns to equilibrium the moment the bottle tilts, so the surface of the water is always horizontal, and the region the water occupies on the base is the part of the base polygon that lies below the surface. While the bottle rolls, that region turns into convex polygons of many shapes.

Jonghun keeps drinking water or refilling the bottle, and he asks for help every time. Each request gives the amount of water inside the bottle. Find the smallest and the largest number of sides the water region can have while the bottle rolls.

The height of the bottle is $1$ cm. When you count the sides of the region, two adjacent sides of its boundary that lie on one straight line count as a single side.

The first line contains the number of vertices of the base of the bottle, $N$ ($3 \le N \le 500{,}000$), and the number of times Jonghun asks for help, $M$ ($1 \le M \le 50$).

Each of the next $N$ lines contains the $x$ coordinate and the $y$ coordinate of a vertex of the base, separated by a space. The base is traced onto a coordinate plane ruled with a $1$ cm grid, and the coordinates are written in the order the vertices are met when walking counter-clockwise from an arbitrary vertex. Every coordinate is an integer between $-100{,}000{,}000$ and $100{,}000{,}000$. No three vertices lie on one straight line.

Each of the following $M$ lines contains one integer $W$, the amount of water inside the bottle for that request. $W$ is at least $1$ and at most the volume of the bottle, measured in cm$^3$.

Print $M$ lines. On line $m$, print the smallest and the largest number of sides that the water region on the base can have when the bottle is laid down and rolled for the $m$-th request, separated by a space.

The picture above shows the water region of the first request of the first example ($W = 18$) forming a triangle, a quadrilateral and a pentagon.