Newspaper Delivery Route

The urban planning for the YZ residential community has adopted a new scheme. The community is enclosed by a white wooden fence whose shape is an arbitrary polygon. Each household is located at a vertex of this polygon while an elegant park is built in its interior. A devoted newspaper delivery man has a peculiar habit: he rides his bicycle along a fixed circular route (i.e. a circle with a fixed but unknown center) and, whenever he sees a house in his right‐hand direction, he tosses the newspaper so precisely that it lands exactly at the doorstep. However, because he cannot distinguish the houses, he only remembers the order in which the post office hands him the newspapers – the order of the vertices of the polygon. As a result, if the order in which the houses appear on his right while riding the circle does not coincide with the given order, some houses will receive the wrong newspaper. Your task is to help him choose a valid circular route.

Interpretation: It turns out that if the center of the circle is chosen appropriately, then as the cyclist rides his circle, the cyclic order of the vertices (when sorted by their polar angles with respect to the center) is exactly the order provided by the post office. A classical geometric fact is that for a simple polygon the cyclic order of the vertices as seen from a point is the same as the order of the vertices of the polygon if and only if the point lies in the kernel of the polygon. (The kernel is the set of all points from which the entire polygon is visible.)

Thus, the problem reduces to: Given a polygon (provided by its vertices – which are the house locations – in the order given by the post office), find all points with integer coordinates that lie in the kernel of the polygon. If there is no such point, output 0.

Note on the kernel: For a polygon with vertices given in counterclockwise order, its kernel is obtained as the intersection of all the half‐planes defined by its edges. For an edge from P_i to P_i+1, the corresponding half‐plane is

\(\{P\mid (P_{i+1}-P_i) \times (P-P_i) \ge 0\}\)

Any point in the kernel will see the vertices in the correct cyclic order.

inputFormat

The first line contains a single integer n (n ≥ 3), which is the number of vertices of the polygon. Each of the next n lines contains two integers, representing the x and y coordinates of a vertex. The vertices are given in the order in which the post office arranges the newspaper deliveries.

outputFormat

Output all integer coordinate points (one point per line, with the x and y coordinates separated by a space) that lie in the kernel of the polygon, sorted in ascending order first by the x-coordinate then by the y-coordinate. If there exists no such point, output a single line containing 0.

sample

3
0 0
2 0
0 2

0 0
0 1
0 2
1 0
1 1
2 0