Given a set of points on the plane. Find the smallest convex polygon containing all these points.
Two variants of the answer are required. In the first variant, you need to select the points that are at the vertices of the desired polygon. In the second answer, you need to select all points that are on the border of the desired polygon — both at the vertices and on the sides.
The first line of the input contains an integer $$$n$$$ — the number of points ($$$3 \le n \le 10^5$$$).
Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the next point ($$$-10^9 \le x_i, y_i \le 10^9$$$).
It is guaranteed that no two points coincide and there exist three points that do not lie on the same line.
In the first line of the answer, output an integer $$$n_1$$$ — the number of points at the vertices of the polygon.
In each of the next $$$n_1$$$ lines, output a pair of integers — the coordinates of the next point in counterclockwise order. The first point should be the lowest, and if there are several such points, then the leftmost one.
In the next line, output an integer $$$n_2$$$ — the number of points at the vertices and on the sides of the polygon.
In each of the next $$$n_2$$$ lines, output a pair of integers — the coordinates of the next point in counterclockwise order. Similarly, the first point should be the lowest, and if there are several such points, then the leftmost one.
61 13 51 47 33 34 2
4 1 1 7 3 3 5 1 4 5 1 1 4 2 7 3 3 5 1 4
Illustration for the example from the statement:
