There are ~N~ points labelled from ~1~ to ~N~. The point labelled ~i~ is located at ~(x_i, y_i)~. These ~N~ points are coloured such that the point labelled ~i~ has colour ~c_i~. There are only two colours, red or blue. If ~c_i~ is ~1~, the point is red and if ~c_i~ is ~2~, the point is blue. It is guaranteed that no two have the same coordinates. Can you choose ~3~ of the ~N~ points such that none of the other ~N-3~ points lie within the interior of the (possibly degenerate) triangle formed by the ~3~ points and such that the colours of the ~3~ points are not all the same? A point on the boundary of the triangle is not considered within the interior of the triangle for this problem. In particular, choosing ~3~ collinear points will guarantee no other points in its interior.
~1 \le c_i \le 2~ for all ~1\le i\le N~
~1 \le x_i, y_i \le 10^6~ for all ~1\le i\le N~
~3 \le N \le 200\,000~
The first line contains a single integer, ~N~.
The next ~N~ lines each contain three space-separated integers, ~x_i~, ~y_i~, and ~c_i~.
If it is not possible to find ~3~ such points, output
-1. Otherwise, print three space-separated integers
i j k on a single line representing the three points chosen. If there are multiple possibilities, any triplet will be accepted. The triplet does not need to be written in any particular order.
Sample Input 1
6 1 1 1 7 7 2 1 7 1 7 1 1 2 3 1 6 5 1
Sample Output 1
2 3 5
Sample Input 2
4 1 1 1 1 2 2 1 3 1 1 4 1
Sample Output 2
1 2 4