Spy Network Plan

Johnny found a large map in the headquarters. Several points on it were marked in two colors, green or red. At the time he paid little attention to it. Later he learned that the map showed two plans for reorganizing a spy network, drawn in different colors.

The main idea of the reorganization is to distribute agents among several points. Each point is managed directly by the headquarters. A point may hold several agents. In that case the point is drawn on the map as many times as the number of agents it must hold.

The territory controlled by a set of points is the smallest convex set by area that contains all the points of the original set. If all the points lie on one line, the territory is the shortest segment of that line that contains all of them.

Johnny remembered where the points were placed, but not which ones belonged to the first plan and which to the second. He also remembered that neither plan could be carried out, because the territories controlled by points from different plans intersected. The last thing he remembered is that the points of one color were far more numerous than the points of the other.

Johnny wants to know how the points could be divided between the plans. Formally, find a partition of the points such that the territories controlled by points of different colors intersect, and the difference between the numbers of points in the two groups is as large as possible.

The first line contains an integer $n$, the number of points ($4 \le n \le 10^5$).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$, the coordinates of a point on the map ($-10^9 \le x_i, y_i \le 10^9$).

It is guaranteed that a valid partition exists.

On the first line, print the integer $m$, the size of the smaller of the two sets.

On the second line, print the $m$ indices of the points in that set.

If several optimal answers exist, you may print any of them.