At the headquarters, Johnny found a large map on which several points were marked in two colors - green or red. At the time, he did not attach much importance to the finding, however, later it turned out that the map depicted two projects to re-equip the spy network, shown, respectively, in different colors.

The main idea behind retooling is to distribute agents across multiple locations. Each point would be controlled directly by headquarters. Each point can contain several agents. In this case, the point was indicated on the map exactly as many times as the number of agents should have been there.

The territory controlled by a set of points is defined as follows: it is the smallest by area convex set of points in the plane, which contains all the points from the original set of points. If all points of the set lie on one straight line, then the shortest segment of this straight line containing all points of the original set is controlled.

Johnny clearly remembered where the points were placed, but which ones matched the first project, and which - the second, he could not remember. He also remembered that both projects was impossible to implement, since the territories controlled by points from different projects intersected.

The last fact that Johnny could remember was that there were many more points of one color than points of another color. Johnny wondered how the points could be distributed among the projects. Formally, Johnny wants to find such a distribution of points that the territories controlled by points of different colors intersect, and the difference between the number of points belonging to different projects is the largest.

Input

The first line contains an integer n (4 ≤ n ≤ 105) - the number of points. Each of the following n lines contains two integers xi and yi (-109 ≤ xi, yi ≤ 109) - coordinates of points indicated on the map. It is guaranteed that the desired partition exists.

Output

In the first line print an integer m - the size of the smaller set of points. On the second line print m numbers - indices of points included in this set. If there are several optimal answers, it is allowed to print any.